Let G be a graph with $n \ge 3$ nodes and with average degree $3\le k\le n$. What are the largest and smallest girth G can have?



Largest girth of a graph of average degree k
You can find your answer in the paper:


**Generalized Girth Problems in Graphs and Hypergraphs**


By Uriel Feige and Tal Wagner.


Let $A\_2(n,k)$ denotes the optimal upper bound for girth of graphs with $n$ nodes and average degree $k$. So, it is proved that we have
$$A\_2(n,k)=\Theta(\log\_{k-1}(n))$$ and it is best possible. Also, finding the best possible constant $c$ of the $log^{n}\_{k-1}$ is an open problem and the best upper bound is $c\leq 2$ and the best lower bound is $c\geq 4/3$.


By Erdos work we have:
$$A\_2(n,k)\leq 4n/k$$.


For some good results you can see the girth of Tanner graphs of Low-density parity check codes and the conditions for having special girth in bipartite graphs.


