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

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