Grinberg-Introduction-Graph-Theory · Problem 5.25

Trees and arborescences

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). [For example, here is how

K_{5,2}

looks like: a bipartite graph with vertices

1,2,3,4,5

on top and

-2,-1

on bottom.] How many spanning trees does

K_{n,m}

have?

Intuitive explanation

A spanning tree of $K_{n,m}$ must connect all $n+m$ vertices using exactly $n+m-1$ edges from the complete bipartite graph. The key insight is that every edge must go between the two parts (positive and negative vertices), so any spanning tree is determined by how many edges connect each positive vertex to the negative vertices—think of it as a flow problem where you're distributing $m$ "connection slots" among $n$ positive vertices such that every vertex gets at least one connection and the graph stays connected. This constraint can be counted using the Matrix-Tree Theorem or a direct combinatorial argument about valid degree sequences in a bipartite tree.

Intuitive explanation

Related theory

Trees Spanning Trees And Minimum Spanning Trees

Browse the problem library