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

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