Graphs with few cycles
Task number: 4221
Count how many different spanning trees has the cycle on \( n \) vertices.
How many spanning trees has the dumbbell, i.e. two cycles of lengths \( m \) and \( n \) connected by a path of length \( l \).
How many spanning trees hass the so-called \(\Theta\)-graph, i.e. two vertices of degree three connected by paths of lengths \( m, n \) and \( l \).
Solution
Cycles: removing any edge creates a panning tree, so there are \( n \). Removing multiple edges would become disconnected.
Dumbbells: One edge must be removed from each of the two cycles. These selections are independent, the resulting number is \( mn \).
\( \Theta \)-graphs: From two paths we remove one edge at a time, we leave the third path untouched so that the graph remains connected. The resulting number of spanning trees is \( mn + ml + nl \).
