I am working on Algebraic Combinatorics by Richard P. Stanley.
Problem 4 on Chapter 9 reads:
Let $p \ge 5$, and let $G_p$ be the graph on the vertex set $\mathbb{Z}_p$ with edges $\{i, i+1 \}$ and $\{i, i+2 \}$, for $i \in \mathbb{Z}_p$. Thus, $G_p$ has $2p$ edges. Show that $G_p$ has $pF^2_p$ spanning trees where $F_p$ is the $p$th Fibonnaci Number (assuming that $F_1 = F_2 = 1, F_3 = 2, \cdots$).
This chapter deals with the Matrix-Tree Theorem. The main formulas provided in this chapter are:
The Matrix Tree Theorem (to count the number of spanning trees)
The Laplacian Graph of a regular graph of degree $d$ can be expressed as: $$L(G) = dI - A(G)$$ where $I$ is the identity and $A(G)$ is the adjacency matrix.
If $G$ is a connected graph on $p$ vertices and the eigenvalues of $L(G)$ are: $$\lambda_1, \lambda_2, \cdots \lambda_p$$ where $\lambda_p = 0$, then the number of spanning trees in $G$ is: $$\frac{1}{p} \prod_{i =1}^{p-1} \lambda_i.$$
I tried working with the Laplacian matrices and the Adjacency matrices and tried using all $3$ of these formulas but was unable to find any patterns.
I feel like Binet's formula is going to be important here in order to represent the Fibonacci Numbers however none of the eigenvalues that I have seen so far seem even somewhat related to the terms in Binet's Formula.
How should I attack this problem?
I found a solution to the problem here.
Summary of the solution in case the link rots: First solve for the "unhooked" graph in which the edges $(p-2,0),(p-1,0)$ and $(p-1,1)$ are removed. ( we get $f_{2n-2} = f_n^2-f_{n-2}^2$ such graphs ). Notice that by rotating this "unhooked" graph that is contained in the circulant one we can get $n(f_n^2 - f_{n-2}^2)$ distinct subtrees. And then in order to get the remaining $n(f_{n-2}^2)$ subtrees do some shenanigans with rotation yet again.