Introduction to Graph Theory · Problem 5.25

Trees and arborescences — Darij Grinberg

Mathematics — Graph Theory · spanning-trees-complete-bipartite

Problem

Let

n

and

m

be two positive integers. Let

K_{n,m}

be the simple graph with

n + m

vertices

1, 2, \ldots, n \qquad \text{and} \qquad -1, -2, \ldots, -m,

where two vertices

i

and

j

are adjacent if and only if they have opposite signs (i.e., each positive vertex is adjacent to each negative vertex, but no two vertices of the same sign are adjacent). How many spanning trees does

K_{n,m}

have?

Related theory

Trees Spanning Trees And Minimum Spanning Trees

Browse the problem library