Erdős–Gyárfás conjecture confirmed for P8-free and P10-free graphs

Statement

The Erdős–Gyárfás conjecture (Erdős, jointly with Gyárfás, 1990s; this is Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle on erdosproblems.com, prize \$1000, still open in general): *every finite graph with minimum degree at least 3 contains a cycle whose length is a power of 2* (i.e. length $4, 8, 16, 32,\dots$).

This is a hard, still-open combinatorial conjecture in full generality. But it has been confirmed for restricted graph classes defined by forbidding a long induced path. For $t\ge 1$, a graph is $P_t$-free if it contains no induced subgraph isomorphic to the path on $t$ vertices ($P_t$). The result on this page:

> Every $P_8$-free graph with minimum degree $\ge 3$ contains a cycle of length 4 or 8 (Gao–Shan, 2021/2022). Every $P_{10}$-free graph with minimum degree $\ge 3$ contains a cycle of length 4 or 8 (Hu–Shen, 2023/2024).

Since 4 and 8 are both powers of 2, both results confirm the Erdős–Gyárfás conjecture on their respective graph classes — and in the *strong* form of exhibiting one of only two specific short lengths, not just "some" power of 2.

Facts

- Origin of the conjecture: Erdős and Gyárfás, restated by Erdős through the 1990s [Er93, Er94b, Er95, Er96, Er97b, Er97c per erdosproblems.com/64]. Full conjecture remains open — see Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle. - **Gao–Shan (2021, published *Graphs and Combinatorics* 2022): Yuping Gao, Songling Shan, "Erdős-Gyárfás Conjecture for $P_8$-free graphs," arXiv:2109.01277 (submitted 2021-09-03), doi:10.1007/s00373-022-02578-9. Theorem: every $P_8$-free graph with $\delta(G)\ge 3$ has a cycle of length 4 or 8. - Hu–Shen (2023, published *Discrete Mathematics* 2024): Zhiquan Hu, Changlong Shen, "Erdős-Gyárfás Conjecture for $P_{10}$-free Graphs," arXiv:2308.05675 (submitted 2023-08-10), doi:10.1016/j.disc.2024.114175. Abstract verbatim: "every $P_{10}$-free graph with minimum degree at least three contains a cycle of length 4 or 8. This implies that the conjecture is true for $P_{10}$-free graphs." Explicitly extends Gao–Shan's $P_8$ result. - Both papers prove the same sharp dichotomy — not just "a power of 2" but specifically "length 4 or 8" — which is stronger than the conjecture demands and is exactly what makes the technique reusable/extendable. - The line continues past this page's scope: Hegde, Sandeep, Shashank (IIT Dharwad), "Erdős-Gyárfás conjecture on graphs without long induced paths," arXiv:2410.22842 (Oct 2024, v2 Feb 2025), pushes the same reduction to $P_{12}$-free (still "cycle 4 or 8") and, with a backtracking computer search, to $P_{13}$-free (general power-of-2 conclusion). Correction from a 2026-07-03 primary-source re-read (see Canonical-augmentation backtracking search for Erdős–Gyárfás minimal counterexamples (P13-free)): both the $P_{12}$ and $P_{13}$ extensions in that paper are pure computer search — there is no hand case-analysis in it at all; the hand "good hole" surgery described in steps 1-7 below is specific to Gao–Shan/Hu–Shen and is explicitly cited by the 2024 paper only as inspiration for the search's design, not reused directly. Public code: github.com/rbsandeep/Erdos-Gyarfas. This confirms the $P_8\to P_{10}\to P_{12}/P_{13}$ line is an active, still-moving research frontier (arxiv.org/html/2410.22842v2, read directly). - Relation to the general conjecture**: these results do *not* resolve Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle (minimum-degree-3, no path restriction) — they resolve it only on the sub-class of graphs additionally forbidding a long induced path. The general conjecture (no $P_t$-freeness assumption) remains open; see Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle for the full literature map (other confirmed restricted classes: claw-free planar, 3-connected cubic planar, various Cayley graphs, diameter-2 graphs).

Solution

Answer: Confirmed (not just "a power-of-2 cycle exists" but the sharp "cycle of length 4 or 8 exists") for $P_8$-free graphs (Gao–Shan 2022) and for $P_{10}$-free graphs (Hu–Shen 2024), both under the conjecture's exact hypothesis $\delta(G)\ge 3$.

The transferable proof technique — minimal-counterexample + shortest-induced-hole surgery, forcing either a short cycle or a too-long induced path:

1. Minimal counterexample reduction. Suppose (for contradiction) $G$ is $P_8$-free (resp. $P_{10}$-free), has $\delta(G)\ge3$, but contains *neither* a $C_4$ nor a $C_8$. The whole proof derives a contradiction from this single assumption — it is enough to rule out exactly these two lengths, because any longer power-of-2 cycle ($C_{16}$, etc.) would itself contain an induced path far longer than 8 or 10 vertices, already violating $P_8$-/$P_{10}$-freeness; so the only two "dangerous" lengths that could hide inside a short forbidden-path graph are 4 and 8.

2. Force a chordless "hole." A standard fact used as the entry lemma (Gao–Shan's Lemma 3.1): minimum degree $\ge3$ together with $C_4$-freeness forces $G$ to contain an *induced* cycle ("hole") $C$ of length $k\ge5$ — take the shortest cycle in $G$; if it had a chord it would yield a shorter cycle, so the shortest cycle is automatically chordless.

3. Extremal choice of the hole ("good hole"). Among all shortest holes, pick one, $C$, that additionally *maximizes* a secondary structural invariant — in Hu–Shen's formalization, $|I_C|$, a count of how much "extra" adjacency (near-triangulation) sits just outside consecutive pairs of hole-vertices. This is the classic extremal/potential-function trick: minimality controls the hole's length; maximality of the secondary invariant controls how the rest of the graph attaches to it, ruling out the worst-case attachment patterns before the case analysis even starts.

4. Degree forces an escape, and hole-minimality keeps the escape "clean." Since $C$ is chordless of length $\ge5$, every vertex of $C$ has only 2 neighbors *on* $C$, so $\delta(G)\ge3$ forces at least one neighbor *off* $C$ for every hole vertex. Because $C$ is a shortest (hence chordless) and extremal ("good") hole, these off-hole neighbors cannot create unwanted shortcuts back into $C$ without either producing a shorter cycle (contradicting minimality) or a bigger triangulation count (contradicting extremality) — so their attachment pattern is tightly constrained.

5. Splice arcs of the hole with off-hole neighbor paths into one long induced path. This is the mechanical core of the argument: take an arc of the chordless hole plus a chain of forced off-hole neighbors ("good paths" in Hu–Shen's terminology), and show the concatenation is itself an *induced* path — because chordlessness of $C$ and the extremal/minimality constraints from steps 2–4 rule out any extra chords that would shrink it. Case-exhaust over the hole's length ($k=5,6,7$ in both papers — longer holes are excluded directly by $P_8$-/$P_{10}$-freeness) and, in Hu–Shen's harder $P_{10}$ case, over an additional configuration (a $\Theta(2,3,3)$-graph, three internally-disjoint paths of length 2,3,3 between two vertices) that can arise when no short hole exists.

6. Every branch closes. Each case in the exhaustion ends in one of exactly three outcomes: (a) an explicit $C_4$, (b) an explicit $C_8$, or (c) an explicit induced path on 8 (resp. 10) vertices — each of which directly contradicts an assumption ($C_4$/$C_8$-freeness or $P_8$/$P_{10}$-freeness). Hence no minimal counterexample exists, proving the theorem.

7. Why this is the transferable idea. The skeleton — *(i) reduce an infinite-target conjecture to ruling out exactly two small witness cycle-lengths; (ii) pick a shortest+extremal "hole" as an anchor; (iii) use the minimum-degree hypothesis to force escaping neighbors; (iv) splice hole-arcs with escaping-neighbor chains into an explicit long induced path, using the hole's extremal properties to guarantee it stays chordless* — is exactly what Hu–Shen reuse (with a strictly harder case analysis, needing the Theta-graph lemma) to go from $P_8$ to $P_{10}$, and what the follow-up 2024 paper (arXiv:2410.22842) mechanizes further with a backtracking search over the same "minimal counterexample" structural constraints to reach $P_{12}$-/$P_{13}$-free. The technique is a general recipe for "prove a min-degree-forces-cycle-length statement on a $P_t$-free class": push $t$ up by (a) extending the case analysis on hole length/configuration one notch, and (b) once the case tree gets too large for hand-proof, hand it to a backtracking/SAT-style search over the same structural invariants. This is directly the attack surface flagged on Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle's "Attack surface" section as a realistic, re-runnable contribution path (push the $P_t$-free line past current frontier, or formalize/reproduce a step in Lean).

Related

- Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — the general (no path-freeness restriction) Erdős–Gyárfás conjecture; still open; this page documents two of its confirmed restricted-class instances. Also lists other confirmed classes (claw-free planar, cubic planar, Cayley graphs, diameter-2) and the computational structural-pruning result (Carr 2026, arXiv:2605.22844) on any hypothetical minimal counterexample to the *general* conjecture. - Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often — the chromatic-number analogue of the power-of-2-cycle theme, fully solved by Liu–Montgomery (arXiv:2010.15802) via a completely different technique (sublinear expanders); useful contrast showing the *unrestricted*-graph route needed a different, heavier tool than the $P_t$-free surgical route documented here. - P_t-free graphs: the Gyárfás path argument (χ-boundedness + minimal-counterexample cycle surgery) — the $P_t$-free ($K_{1,m}$-free, claw-free, etc.) restricted-class proof line this page belongs to ($P_8\to P_{10}\to P_{12}/P_{13}$), each instance reducing to "exhibit a cycle of length 4 or 8." - Structural constraints on a hypothetical minimal counterexample (minimum-degree, connectivity, adjacency pruning) — the general method (assume smallest violating graph, derive structural constraints, contradict) shared with Markström's and Carr's structural-pruning results on the full (non-$P_t$-free) conjecture. - Discharging method — charge-counting technique for planar/structural graph coloring and cycle-existence proofs — a related but distinct extremal/potential-function technique (used e.g. by Heckman–Krakovski for 3-connected cubic planar graphs); the "good hole" extremal-invariant trick here (step 3 above) is the same broad family of idea (maximize/minimize a secondary structural invariant subject to a primary minimality constraint) specialized to induced-cycle surgery rather than planar discharging. - Canonical-augmentation backtracking search for Erdős–Gyárfás minimal counterexamples (P13-free) — deep-read of the follow-up paper (arXiv:2410.22842, primary-source HTML read 2026-07-03): full explore(G,k) backtracking pseudocode, runtimes (11h56m serial / 17m17s parallel at $P_{13}$), the out-of-memory (not structural) wall at $P_{14}$, public code (github.com/rbsandeep/Erdos-Gyarfas), and the paper's own use of the Markström graph (24-vertex, $C_4$/$C_8$-free, $P_{18}$-free with induced $P_{17}$) as a correctness test — the same construction this wiki uses as the $\le P_{17}$ ceiling witness on Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle.