Understanding the formular $1/8(tr(A^4_G)-2|E|-4\sum_{v\in V} \binom{deg_G(v)}{2} )$ for the number of cycles of length 4 in G

Question

So here is the formular I am trying to understand:

Let G = (V,E) be a graph, with an adjacency matrix $A_G$. The number of cycles with a length of 4 in G is the result of the following calculation:

$$\frac{1}{8}\left(\operatorname{tr}(A^4_G)-2|E| -4\sum_{v\in V} \binom{\deg_G(v)}{2}\right)$$

What I do understand so far, is that the i'th entry of the trace of the adjacency matrix $A^4_G$ shows the number of walks of length 4 that start in $v_i$ and end in $v_i$. Since these aren't necessarily cycles, I have to subtract all walks of length 4, that aren't cycles. I therefore subtract two times the number of edges in G, i.e. (-2|E|), since each edge is connected to two vertices and each $v_i$ has a walk of length 4 that ends in $v_i$ through moving back and forth on the same edge. The walks of length 4 that I still need to subtract, are probably the ones of the form $v_i->v_j->v_i->v_x->v_i$, as they aren't cycles either. This is probably what $-4\displaystyle\sum_{v\in V} \binom{\deg_G(v)}{2}$ is for, but I can't seem to understand the logic behind it. Why does this formular succeed to sum up the number of walks of the form $v_i->v_j->v_i->v_x->v_i$ in the given graph? Also, why do I have to divide the end result by 8?

Answer 1

Your logic is basically sound. The count $4\displaystyle\sum_{v\in V} \binom{\deg_G(v)}{2}$ is actually responsible for removing two different types of walks:

1. $v_i \rightarrow v_j \rightarrow v_i \rightarrow v_k \rightarrow v_i$, with $i,j,k$ distinct: there are $2\displaystyle\sum_{v\in V} \binom{\deg_G(v)}{2}$ walks of this form; for each vertex $v$ serving as the initial vertex of the walk, choose two edges to be the distinct edges of the walk, which can be done in $\binom{\deg_G(v)}{2}$ ways. There are then two ways to pick which edge is walked first.
2. $v_i \rightarrow v_j \rightarrow v_k \rightarrow v_j \rightarrow v_i$, with $i,j,k$ are distinct: again for each vertex $v$ serving as the middle vertex $v_j$, there are $\binom{\deg_G(v)}{2}$ ways to pick the edges of the walk. There are then two ways to pick which is the initial vertex of the walk, again yielding $2\displaystyle\sum_{v\in V} \binom{\deg_G(v)}{2}$ walks of this form.