# Prove that a connected graph exists with $k$ spanning trees

I need to prove that a connected graph exists such that it has exactly $$k$$ spanning trees ( for $$k \neq 2$$)

my proof:

Each cycle in a graph is connected, because a cycle is a set of edges such that one edge is connected to the other edge's tail, and the vertices are unique (no repetitions). Each cycle with length $$k$$ has exactly $$k$$ spanning trees and they are, all the $$k$$ options to start from ($$k$$ vertices in the cycle to start from) meaning that for any $$k \neq 2$$ I can find a connected graph with $$k$$ spanning trees.

I would like to hear your thoughts... Thank you!

• Yes, this is fine. Jul 26, 2020 at 17:17
• @BrianM.Scott Thank you very much sir! Jul 26, 2020 at 17:20
• You’re very welcome. Jul 26, 2020 at 17:20

Going by it, if $$A(G)$$ is the adjacency matrix of a connected graph and $$\lambda_1, \lambda_2,...,\lambda_n$$ are its non-zero eigenvalues, then the number of spanning trees of $$G$$ is
$$\tau(G)=\frac{1}{n}\lambda_1 \cdot\lambda_2\cdot... \cdot\lambda_{n-1}.$$
Using this you can verify that your proposed graph does indeed have $$k$$-spanning trees, but perhaps can find more graphs with $$k$$ spanning trees using this.