Erdős Problem 752: many cycle lengths from degree and girth
1. Statement and result
For fixed positive integer $s$, does minimum degree at least $k$ and girth greater than $2s$ force $\Omega_s(k^s)$ distinct cycle lengths? Yes. We give a complete proof of this original counting assertion, reconstructing the expansion and breadth-first-level argument of Sudakov and Verstraëte. A depth-first-search lemma proved here suffices; their stronger assertion about consecutive even lengths is not needed. This distinction also avoids the erroneous general theta-graph path lemma in the original paper. The authors' addendum corrects that lemma for their stronger results. No form of that lemma is used below.
2. Moore bound and expansion
A graph of girth greater than $2s$ and minimum degree at least $d+1$ has more than $d^s$ vertices. Indeed, expose the breadth-first tree from a root through depth $s$. Every vertex at depth less than $s$ has at least $d$ unused forward neighbors, except that the root has at least $d+1$. A repetition or extra edge invalidating this count would yield a cycle of length at most $2s$. Thus the distinct vertices number at least \[
1+(d+1)(1+d+\cdots+d^{s-1})>d^s. \tag{1}
\] Let $J$ have the same girth and minimum degree at least $6(d+1)$. For every nonempty set $X$ with $|X|\le d^s/3$, its external neighborhood $\partial X$ satisfies \[
|\partial X|>2|X|. \tag{2}
\] Otherwise $Y=X\cup\partial X$ has at most $3|X|$ vertices, and every edge incident with $X$ lies in $J[Y]$. Counting such incidences shows \[
e(J[Y])\ge\tfrac12\sum_{x\in X}\deg_J(x)
\ge3(d+1)|X|\ge(d+1)|Y|.
\] Repeatedly delete vertices of degree less than $d+1$. This cannot delete the whole graph: such a deletion order would count fewer than $(d+1)|Y|$ edges. A nonempty remaining graph has minimum degree at least $d+1$ and, by $1$, more than $d^s$ vertices. This contradicts $|Y|\le d^s$ and proves $2$.
3. Expansion gives a long path, directly
Suppose $2$ holds for every $1\le|X|\le m$, where $m$ is an integer. Run the usual depth-first search, maintaining the active root-to-current-vertex path as a stack. Upon finishing a vertex, pop it and put it in the finished set. At the moment exactly $m$ vertices are finished, every neighbor of the finished set outside that set is on the active stack: an edge from a finished vertex to a still unvisited vertex would contradict completion of that vertex's search. By $2$, the stack has more than $2m$ vertices. It is a simple path and therefore has at least $2m$ edges. The required moment exists because $2$ rules out a graph of at most $m$ vertices. Restarting the search in a new component causes no problem: previously finished components have no neighbors outside themselves. This proves the path lemma without importing a rotation or theta-graph theorem.
4. Keeping a long path inside two distance levels
It suffices to assume that $G$ has average degree at least $48(d+1)$ and girth greater than $2s$. A random bipartition retains half its edges on average; choose a bipartite subgraph retaining at least half, and a connected component $F$ of average degree at least $24(d+1)$. Take a breadth-first spanning tree of $F$ with levels $L_0,L_1,\ldots$. Because $F$ is bipartite, every edge joins consecutive levels. If $F_i=F[L_i\cup L_{i+1}]$, then \[
\sum_i e(F_i)=e(F)\ge12(d+1)|V(F)|,
\qquad \sum_i|V(F_i)|\le2|V(F)|.
\] Consequently some $F_i$ has average degree at least $12(d+1)$. Deleting vertices of degree less than $6(d+1)$ leaves a nonempty subgraph $J$ of minimum degree at least $6(d+1)$; the edge-count argument is the same as above. Put $m=\lfloor d^s/3\rfloor$. By $2$ and the depth-first lemma, $J$ contains a path $P$ with at least $2m$ edges. Because $P$ alternates between $L_i$ and $L_{i+1}$, the set $W=V(P)\cap L_i$ has at least $m$ vertices.
5. Closing many different subpaths
Assume $m\ge2$. In the breadth-first tree take the smallest subtree connecting $W$. All members of $W$ have the same depth, so they are leaves of this subtree, whose root is their least common ancestor. It has at least two branches containing members of $W$. Partition $W=A\sqcup B$ by taking $A$ to be the leaves in one such branch and $B$ the other leaves; choose the branch so that $|B|\ge|W|/2$. Both parts are nonempty. Every tree path joining $a\in A$ to $b\in B$ has the same length $2h$, and all its internal vertices have depth less than $i$. Fix $a\in A$. At least $|B|/2$ vertices of $B$ lie on the same side of $a$ along $P$. Their $a$--$b$ subpaths in $P$ have pairwise different lengths. Each such subpath lies in $L_i\cup L_{i+1}$, so its union with the tree path between its endpoints is a simple cycle. Adding the same $2h$ to these different subpath lengths preserves distinctness. We obtain at least \[
|B|/2\ge |W|/4\ge m/4
\] distinct cycle lengths, all even. For a graph of minimum degree $k$, take $d=\lfloor k/48\rfloor-1$. For all sufficiently large $k$, the argument applies and gives \[
|C(G)|\ge\frac14\left\lfloor\frac{(\lfloor k/48\rfloor-1)^s}{3}\right\rfloor
=\Omega_s(k^s).
\]
6. Sources and assessment
Sources:
https://www.erdosproblems.com/752; B. Sudakov and J. Verstraëte,
Cycle lengths in sparse graphs,
https://arxiv.org/abs/0707.2117, especially Theorem 2.2; their
Addenda,
https://www.math.ethz.ch/~sudakovb/addenda.pdf. The constant may depend on fixed $s$, as indicated. The lower-level tree paths are internally disjoint from $P$; omitting that check would not justify simple cycles. The proof establishes the original requested asymptotic count and makes no claim to reconstruct the stronger consecutive-length theorem.
SOLVED: minimum degree $k$ and girth greater than $2s$ force $\Omega_s(k^s)$ different cycle lengths.
Completion rate estimate: 100%.