# 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!

## 1 Answer

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
• @OnAndOff Yes, I think it does count. Maybe just start by mentioning that a cycle is connected. The length of this proof really depends on what you can assume as having been proved in the past and how much of it you need to refer to explicitly in a homework. – Alexander Burstein Jul 12 '20 at 17:24