# Number of 4 cycles

Let $$C_4$$ be a cycle with four vertices. For an arbitrary graph $$G$$ with $$n$$ vertices and m edges say $$m>n\sqrt n$$, how many $$C_4$$s exist? Is there a lower bound for this?

• Oct 15 '18 at 17:04

## 1 Answer

Yes, this is known. For $$d = \Omega(n^{1/2})$$ with a sufficiently large implicit constant, any $$n$$-node graph of average degree $$d$$ has $$\Omega(d^4)$$ total $$C_4$$s. This is best possible because it's realized by a random graph.

The earliest reference I'm aware of for this is "Cube-Supersaturated Graphs and Related Problems" by Erdos and Simonovits, where it's claimed without proof. There are many proofs out there, off the top of my head see Lemma 3 here.