Let $G$ be a k-regular graph. Show the exact relationship between $tr(A^4)$ and the number of 4-cycles in $G$.
I understand how $tr(A^4)$ tells us the total number of closed paths of length 4 in $G$, but that doesn't seem useful since that includes, among other things, 4-cycles along one edge.
There are exactly $|v|^2=k^2$ options for closed walks beginning with $v$ and ending with $v$ that are not $4$-cycles. So, each entry of the diagonal of $A^4$ will have an extra $k^2$ walks that are not $4$-cycles, which means that if $a_i$ is the number of $4$-cycles beginning and ending with vertex $i$, we can rewrite the $i^\text{th}$ diagonal entry as $a_i+k^2$. So, $$\operatorname{tr}(A^4)=\sum_{i=1}^{|G|}\left(a_i+k^2\right)=|G|k^2+\sum_{i=1}^{|G|}a_i$$ We've counted every $4$-cycle exactly $4$ times in $\sum_{i=1}^{|G|}a_i$, so letting $X$ be the total number of $4$-cycles in $G$, we get $$\operatorname{tr}(A^4)=|G|k^2+4X$$