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’)| \).

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email