I wish to know the latest bound on the number of edges a graph of girth greater than or equal to $t$ can have.
Specifically, I heard somewhere that a graph of girth greater than or equal to $t$ can have $O(n^{2-\frac{2}{t}})$ edges. Is it true?
I wish to know the latest bound on the number of edges a graph of girth greater than or equal to $t$ can have.
Specifically, I heard somewhere that a graph of girth greater than or equal to $t$ can have $O(n^{2-\frac{2}{t}})$ edges. Is it true?
A graph of girth $g$ can have at most $O(n^{1+\frac1{\lfloor\frac{g-1}2\rfloor}})$ edges. This is known as the Moore bound, though now the only reference I could find online right now is this one: Dutton and Brigham - Edges in graphs with large girth.
Start with a graph $G$ with average degree $d$. By deleting low-degree vertices, you can pass to a subgraph $G'$ with minimum degree $d/2$. Fixing some vertex $v_0$ in $G'$, we should have that there are $\ge (d/2-1)^i$ vertices at distance $i$ from $v_0$, for every $i\le \lfloor (g-1)/2\rfloor$ (this is proven by induction since otherwise you would create a cycle of length $\le g$, if there was some vertex at distance $i<\lfloor (g-1)/2\rfloor$ which had $\ge 2$ neighbors at distance $\le i$ to $v_0$).
Thus, we see that $|V(G')|\ge (d/2-1)^{\lfloor (g-1)/2\rfloor}$. This recovers the bound domotorp mentioned.