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

Question

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!

Answer 1

I would like to offer a different approach which I think is very interesting. This is based on Kirchoff's Theorem, also known as the matrix tree theorem.

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.