Let G be a graph. Prove the following formula for the number of cycles of length 4 in G (not necessarily induced): 1 8 trace A 4 G 2 | E ( G ) | 4 v V ( G ) deg G ( v ) 2 . Here A 4 G is the 4th power of the adjacency matrix, and trace A 4 G denotes the sum of the elements on the main diagonal of A 4 G . For the definition of deg G ( v ), see the next section. Note that this gives an O ( n 3 ) algorithm for counting the number of cycles of length 4, or even a faster algorithm using algorithms for fast matrix multiplication