Graph with n spanning trees
Task number: 4222
For which \( n \) is there a graph with exactly \( n \) different spanning trees?
Solution
For \( n = 1 \) you can choose any tree, these are graphs with exactly one spanning tree.
For \( n \ge 3 \), the cycle \( C_n \) can be choosen.
A simple graph with exactly two spanning trees does not exist - it would have to have at least one cycle, and therefore at least three spanning trees.
(If we allow multiple edges, then such a graph exists - just take a tree and double any edge in it.)
