In a paper I am reading, the author states:
"It is simple and well known that a graph of girth $g$ and $q$ vertices has at most $q^{1+(O(1)/g)}$ edges"
He says that a proof can be found on Extremal Graph Theory, by Bela Bollobas.
However, I do not have easy access to that book.
Could someone please direct me to a more common graph theory book that has this result?
(btw: Modern Graph Theory, by Bollobas, does not have the result, as far as I can tell. But then again, I have not finished searching the book for it, and might have missed it)
Suppose we have a graph with $q$ vertices and girth $g$. Since it has large girth, it must be locally treelike - there cannot be two paths of length $< \frac{g}{2}$ between any pair of vertices, since this would create a cycle of length less than $g$. Hence when we expand the first $\lfloor \frac{g-1}{2} \rfloor \ge \frac{g}{2} - 1$ neighbourhoods of a vertex $v$, there are no collisions - the neighbours of one vertex are disjoint from all others.
If the graph $G$ had minimum degree $d$, then since at every step each vertex contributes at least $d$ distinct neighbours, there must be at least $d^{\frac{g}{2} - 1}$ vertices in the final neighbourhood. As there are only $q$ vertices in total, it follows that $d^{\frac{g}{2} - 1} \le q$, or $d \le q^{\frac{2}{g-2}}$.
This was assuming a minimum degree condition. However, every graph with $q$ vertices and $m$ edges has a subgraph with minimum degree at least $\frac{m}{q}$ (iteratively delete any vertices with smaller degree, which causes us to lose fewer than $\frac{m}{q} \cdot q = m$ edges, and hence there must be a nonempty subgraph left). Thus $\frac{m}{q} \le q^{\frac{2}{g-2}}$, which gives $m = q^{1 + \frac{2}{g-2}} = q^{1 + O(1)/g}$.
However, this bound is not sharp - even if you do not estimate $\lfloor \frac{g-1}{2} \rfloor$, and handle the cases of $g$ even and odd properly, when passing to a subgraph of large minimum degree, this minimum degree is half of the average degree of the original graph. On the other hand, the expanding neighbourhood calculations are tight when the graph is regular, which would suggest the minimum degree should be close to the average degree.
This gap was resolved in the following paper of Alon, Hoory and Linial: paper available here.