1
$\begingroup$

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!

$\endgroup$
3
  • 4
    $\begingroup$ Yes, this is fine. $\endgroup$ – Brian M. Scott Jul 26 '20 at 17:17
  • $\begingroup$ @BrianM.Scott Thank you very much sir! $\endgroup$ – MathAsker Jul 26 '20 at 17:20
  • 2
    $\begingroup$ You’re very welcome. $\endgroup$ – Brian M. Scott Jul 26 '20 at 17:20
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is way more advanced than what we know haha but hope one day I will get to it ;) Thank you! $\endgroup$ – MathAsker Jul 26 '20 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.