= Four-cycle counting by common neighbours
{title2=$C_4(G)=\tfrac12\sum_{i<j}\binom{r_{ij}}2$}
For a simple <graph>, let $r_{ij}$ count the common neighbours of vertices $i,j$. Choosing two such neighbours makes a four-cycle, and each cycle is counted twice through its opposite pairs. The displayed identity follows even when extra edges are present, since cycles are counted as subgraphs rather than induced subgraphs. Also $\sum_{i<j}r_{ij}=\sum_v\binom{d(v)}2$. Applying <Cauchy-Schwarz inequality> to degrees and <Jensen inequality> to common-neighbour counts gives extremal edge and cycle bounds.
Back to article page
