Spanning trees of 2-connected graphs
Task number: 3966
Prove that every vertex 2-connected graph on \( n \) vertices has at least \( n \) spanning trees. When does equality occur?
Solution
By induction according on the number of ears.
Equality applies to the cycle.
If the graph \( G’ \) is created by removing from \(G\) ear with \(t \) vertices, then each spanning tree of \( G’\) can be extended in \( t + 1 \) ways to the spanning tree of \( G \) by adding the whole ear up to one edge. (The graph \( G \) may have other spaning trees containing the entire ear.)
The bound then follows straightforwardly from the inequalities \( \kappa (G) \ge (t + 1) \kappa (G’) \) and \( \kappa(G’) \ge |V(G’)| \).
