spectrum of a regular graph and its girth How we can find the girth (the shortest cycle) of a regular graph from its adjacency spectrum? I know we can find the number of closed walks of length $k$ by:
$$\operatorname{tr}(A^k)= \displaystyle\sum_{i=1}^n \lambda_i^k(A)$$
But how I use the regularity of the graph? The second question is, the closed walks of length 3 in complete graph $K_4$ is 24? I can't find all of them in $K_4$.
 A: The shortest odd cycle is easy to find if you know the number of closed walks of length $k$, for all $k$. The shortest closed walk of odd length is always a cycle; therefore we are looking for the smallest odd $k$ for which $\operatorname{tr}(A^k) > 0$.
For the shortest even cycle, things are more complicated, because there are many closed walks of even length to consider that don't have any even cycles included. The logic here is:

*

*We compute the number of guaranteed closed walks in an $r$-regular graph, that just come from going in a direction and backtracking.

*The first value of $k$ for which this number disagrees with the actual number of closed walks is going to be the length of the shortest cycle.

The hard part of applying this method is counting the number of guaranteed closed walks starting and ending at each vertex: equivalently, the number of closed walks of length $2k$ starting and ending at the root of an infinite $r$-regular tree. Some generating functions for this quantity exist, related to the Catalan numbers but more complicated.
