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

<p>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 <a href="https://arxiv.org/pdf/1710.03164.pdf" rel="noreferrer">here</a>.</p>

CC BY-SA 4.0
2018-10-15T15:03:25.843Z
2018-10-15T15:11:25.117Z
2018-10-15T15:11:25.117Z
GMB
<p>Let <span class="math-container">$C_4$</span> be a cycle with four vertices. For an arbitrary graph <span class="math-container">$G$</span> with <span class="math-container">$n$</span> vertices and m edges say <span class="math-container">$m&gt;n\sqrt n$</span>, how many <span class="math-container">$C_4$</span>s exist? Is there a lower bound for this?</p>

CC BY-SA 4.0
2018-10-15T17:04:46.013Z
Is this [a research-level question in theoretical computer science](https://cstheory.meta.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/235#235)?
Peter Mortensen
<graph-theory><graph-minor>
Number of 4 cycles
shahrzad haddadan
# Number of 4 cycles

(Asked by: username_0 on 2018-10-15)

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?

**Tags:** graph-theory, graph-minor
> **Comments:**
> **username_1**: Is this [a research-level question in theoretical computer science](https://cstheory.meta.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/235#235)?  

---

## 1 answers

### Answer by username_2 on 2018-10-15. Score: 20 | Accepted 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](https://arxiv.org/pdf/1710.03164.pdf).


---

