Let G be a graph with $n\ge 4$ vertices, m edges, and no 4-cycles. Prove $m \le \frac{n}{4} (1+\sqrt{4n-3})$

Question

For any 4 vertices, there must be at most 4 edges, but then I’m stuck. Any hint would be appreciated! No complete solutions please. :)

Answer 1

Hint: Count the number of paths of length 2. The idea being for any pair $(u,v)\in V^{(2)}$, there is at most one vertex $w$ making $uwv$ a path of length 2 so you have some control there too.