Erdős Problem 751: a bounded gap between cycle lengths
1. Statement and answer
For a $4$-chromatic graph list its different cycle lengths as $\ell_1<\ell_2<\cdots$. Can the least consecutive difference be arbitrarily large, even when the girth is large? No: there are always two cycle lengths differing by one or two, and hence some consecutive difference is at most two. The general minimum-degree theorem is due to Bondy and Vince. We reconstruct the induced-cycle argument needed for a $4$-critical subgraph, including its structural lemma, so no external cycle theorem is assumed.
2. Reduction to a $2$-connected graph of minimum degree three
In a finite $4$-chromatic graph, choose a vertex-minimal induced subgraph $H$ of chromatic number four. For each vertex $v$, $H-v$ is $3$-colorable, so $\deg_H(v)\ge3$: otherwise a color missing from its at most two neighbors extends the coloring. Also $H$ is connected. If $v$ were a cut vertex, the subgraphs induced by $v$ and the separate components of $H-v$ would all be proper subgraphs and hence $3$-colorable. Permute their colors so that $v$ has the same color in each, then combine them to color $H$ with three colors, a contradiction. Thus $H$ is $2$-connected and $\delta(H)\ge3$. For an infinite graph of chromatic number four, the standard compactness theorem for finite colorings first gives a finite subgraph that is not $3$-colorable; its chromatic number is four. This compactness input is needed only if infinite graphs are included in the question.
3. An induced cycle with connected exterior
We prove that a finite $2$-connected graph $H$ of minimum degree at least three has an induced cycle $C$ for which $H-V(C)$ is connected. For any induced cycle $C$, its bridges are the components of $H-V(C)$ together with their incident edges and attachment vertices on $C$. There are no chord bridges because $C$ is induced. Each bridge has at least two distinct attachments, since a single attachment would be a cut vertex. Also there is at least one bridge: otherwise an induced cycle would span $H$, forcing every degree to be two. Among all pairs consisting of an induced cycle and one of its bridges, choose $(C,B)$ with the number of vertices of $B$ outside $C$ as large as possible. Let $S$ be $B$'s attachments. Suppose a different bridge $B'$ exists, with attachments $S'$. Choose distinct $x,y\in S'$ and a simple $x$--$y$ path $P'$ whose internal vertices are inside that component of $H-V(C)$. We claim $S\subseteq\{x,y\}$. Otherwise choose $z\in S\setminus\{x,y\}$, and take the $x$--$y$ arc $P$ of $C$ that avoids $z$. The union $P\cup P'$ is a cycle. Repeatedly use a chord to shorten a cycle until an induced cycle $D$ remains, with $V(D)\subseteq V(P\cup P')$. All internal vertices of $B$, together with $z$, lie outside $D$ and are connected: $B$'s interior is connected and $z$ has a neighbor in it. They therefore belong to one component of $H-V(D)$, producing a bridge of $D$ with strictly more internal vertices than $B$. This contradicts maximality and proves the claim. Because $|S|\ge2$, the claim forces $S=\{x,y\}$. Applying it to every pair of distinct points in $S'$ forces $S'=S$. The same argument applies to every bridge other than $B$. Thus all bridges would attach only at the same two points $x,y$. Any other vertex of the cycle, which has at least three vertices, would have only its two cycle neighbors, contradicting minimum degree three. There is therefore exactly one bridge, as required. Moreover, every vertex of $C$ is an attachment of that bridge: otherwise its degree is again exactly two.
4. Two nearby cycle lengths
Write $h=|C|$. If $h$ is odd, choose two cycle vertices $x,y$ whose two arcs have lengths $(h-1)/2$ and $(h+1)/2$. If $h$ is even, choose them so that the arc lengths are $h/2-1$ and $h/2+1$; these are positive since an even cycle has length at least four. Both $x$ and $y$ attach to the unique connected component of $H-V(C)$, so there is a simple $x$--$y$ path $Q$ with all internal vertices outside $C$. Joining $Q$ to either arc gives a simple cycle. Their lengths differ by one in the odd case and by two in the even case. These cycles also lie in the original graph. If two members $a<b$ of an ordered set of cycle lengths have $b-a\le2$, the sum of the consecutive gaps between them equals $b-a$, so one consecutive gap is at most two. Hence the question's minimum cannot tend to infinity, regardless of girth.
5. Attribution and assessment
Sources:
https://www.erdosproblems.com/751; J. A. Bondy and A. Vince,
Cycles in a graph whose lengths differ by one or two, J. Graph Theory 27 $1998$, 11--15,
https://people.clas.ufl.edu/avince/files/Cycles.pdf. The proof above specializes and expands the maximum-bridge argument behind their Lemma 1. It does not claim that the bound two is optimal within the narrower class of $4$-chromatic graphs, and does not need such optimality.
SOLVED: the least gap is at most two. For finite graphs the proof is self-contained; the optional infinite extension uses the stated coloring compactness theorem.
Completion rate estimate: 100%.