Prove that a graph has no more than $n+n^{4/3}$ edges.

Question

In a graph on $n$ vertices all cycles have length at least $7$. Prove that a graph has no more than $n+n^{4/3}$ edges.

Where do I start?

Answer 1

The smallest cycle length is known as the girth of the graph, and it has been shown that an upper bound for the maximum number of edges in a graph with $n$ verticies and girth $g=2k+1$ is actually $^{[1]}$: $$\frac{1}{2}\left(n+n^{1+1/k}\right)$$ In your case, $g=7, k=3$, so the maximum number of edges is actually half what you stated: $$\#\text{edges}_{max}=\frac{1}{2}\left(n+n^{4/3}\right)$$

^[1] Theorem 4.1 of The history of degenerate (bipartite) extremal graph problems.