Number of spanning trees of a bipartite graph
Task number: 4539
How many different spanning trees does the graph \(K_{2,n}\) have? How many of them are non-isomorphic?
Solution
Let us denote the vertices of the smaller part by \(u,v\). These must be connected by a path, this can be chosen in \(n\) ways. Each of the remaining \(n-1\) vertices can be connected either to \(u\) or to \(v\), giving a total of \(n2^{n-1}\) possibilities.
Non-isomorphic spanning trees differ only by splitting the \(n-1\) vertices into two groups. These are \(\lfloor\frac{n}2\rfloor\) possibilities.
Answer
There are \(n2^{n-1}\) spanning trees, only \(\lfloor\frac{n}2\rfloor\) of them are non-isomorphic.
