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.
Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email