maximal girth $g(n,m)$ of a graph with $n$ vertices and $m$ edges The girth of a graph is the length of its smallest cycle.

For $m \ge n \ge 3$, let $g(n,m)$ denote the maximal girth over all graphs with $n$ vertices and $m$ edges. 

Is it true that if $m &gt; c n $ and $c &gt; 1$, then the girth is $O( \log n)$? (I.e. is there a constant $C$ which depends on $c$ but not on $n$ such that $g(n,m) &lt; Cn$?)

Here is a sketch of a proof if $m &gt; cn$ and $c &gt; 2$. Such a graph has average degree $$d = 2m/n &gt; 4.$$ Than a standard fact in graph theory (e.g. by repeatedly deleting vertices of small degree) gives that there is a subgraph $H$ with minimum degree $\delta [H] \ge d/2 &gt; 2$. Since $\delta$ is an integer, $\delta [H] \ge 3$. Now consider a vertex $v \in H$ as a root, consider neighbors of $v$ and their neighbors, etc. Until there is a cycle, every vertex at distance $d$ from $v$ has at least two neighbors at distance $d+1$. So the number of vertices doubles at each step, and the diameter is at most $\log_2 n$. The girth is at most $2 \log_2 n + 1$.
Take a graph $G$ with $n$ vertices and $m$ edges, satisfying $m &gt; cn$. By deleting vertices with degree at most $1$, we get a graph $G'$ with $n' = n-k$ vertices and $m' \ge m-k$ edges, which means $m' &gt; cn'$.

The resulting graph $G'$ has minimum degree $2$ (and some vertices of higher degree), which means we can think of it as a subdivision of a multigraph $H$ with minimum degree $3$. We'd like to pass to that multigraph by smoothing out all degree $2$ vertices, but before we do that, we'd like to make sure that no edges of $H$ correspond to very long paths in $G'$.

Suppose $G'$ contains a path with $t &gt; \frac{c}{c-1}$ edges, all of whose vertices, except the endpoints, have degree $2$. Deleting this path reduces the number of vertices by $t-1$ and the number of edges by $t$, producing a graph $G''$ with $n''=n'-(t-1)$ vertices and $m''=m'-t$ edges. If $t &gt; \frac{c}{c-1}$, then $t &lt; c(t-1)$, which means $m'' &gt; cn''$.

Once no such paths are left, we can smooth out $G''$ to get a multigraph $H$ with minimum degree $3$, all of whose edges correspond to paths in $G''$ of length at most $\frac{c}{c-1}$. We can actually assume $H$ is a graph: it might have loops or parallel edges, but if it does, then they correspond to a cycle in $G''$ of length at most $\frac{2c}{c-1}$.

Now, by the argument in the question, $H$ has a cycle of length at most $2\log_2n + 1$. This corresponds to a cycle in $G''$ (and therefore a cycle in $G$) of length at most $\frac{c}{c-1}(2\log_2n +1)$, because each edge of the cycle in $H$ corresponds to at most $\frac{c}{c-1}$ edges in $G$.
In a cycle of n vertices, the girth is of n. Hence, an upper bound of O($log_{2}n$) on girth size won't exist. The problem with answer given by Misha Lavrov is that when we remove vertices with degree equal to 1, there might be a decrease in degree of remaining vertices.