Show that if graphs are cospectral then they have the same odd girdth Graphs are cospectral if they have the same set of eigenvalues together with their algebraic multiplicities. How can one show that graphs such as these have the same odd girth?
 A: Let $A$ be the adjacency matrix of one graph $G$, and $B$ the adjacency matrix of another graph $H$ which is cospectral to $G$. Thus $\text{tr}(A^k)=\text{tr}(B^k)$ for all nonnegative integers $k$. 
Recall that the $(i,i)$-entry of $A^k$ is the number of walks of length $k$ starting and ending at vertex $i$. Similarly for $B$ of course.
Without loss of generality, suppose that the odd girth $g$ of $G$ is smaller than the odd girth of $H$. So we know there exists at least one closed walk of length $g$ in $G$ and so  $\text{tr}(A^g)> 0$.
On the other hand, there cannot be any closed walks of length $g$ in $H$ since the odd girth of $H$ is larger than $g$ and so any closed walk of length $g$ could only consist of even cycles or repeated edges, in which case the walk would be of even length$^*$, contradicting the oddness of $g$. Hence $\text{tr}(B^g)=0$, contradicting the fact in the first paragraph above.
$*$ This part should be argued more rigorously than I have done, but that's the idea. 
