# Prove a graph has exactly $k$ spanning trees

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!

The $$k$$-cycle has exactly $$k$$ spanning trees, all $$k$$-paths.
• Yes but I don't think I understood how to prove it, is it this just one simple line? what is a $k$-cycle (There might be language barriers) is it a cycle that is made up from $k$ vertices? Thank you sir. – OnAndOff Jul 12 '20 at 16:58
• @OnAndOff A $k$-cycle is a cycle on $k$ vertices (and $k$ edges). A $k$-path is a path on $k$ vertices (and $k-1$ edges). A tree on $k$ vertices has $k-1$ edges, thus exactly $1$ edge must be removed to obtain a spanning tree. Thus, there are exactly $k$ ways to do it in a $k$-cycle. In fact, the removal of any of the $k$ edges in the $k$-cycle yields a path, and a path is a tree. Hope that clarifies things. – Alexander Burstein Jul 12 '20 at 17:08
• Thank you for answering sir, but does that count as an acceptable proof? Because as I view this, it is just saying that for each $k$ cycle it has $k$ spanning trees - doesn't that what we are supposed to prove? and if not, does that really count as a proof? Thank you again sir. – OnAndOff Jul 12 '20 at 17:15