Prove a graph has exactly $k$ spanning trees

162 Views Asked by At

Let $k$ be a positive integer, prove there a connected graph with exactly $k$ spanning trees ($ k \neq 2$)

I tried to prove it by myself but to no avail, I tried to say that for each vertex we can join another new vertex $u$ and thus the graph is still connected and the spanning trees have one more vertex to start from, however I am completely unsure if this implies it has exactly $k$ spanning trees as the question says.

Thank you in advance!

1

There are 1 best solutions below

4
On

The $k$-cycle has exactly $k$ spanning trees, all $k$-paths.