Carr — any minimal Erdős–Gyárfás counterexample is predominantly cubic

Statement

Fix the (still-open) Erdős–Gyárfás conjecture (Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle): every finite graph with minimum degree $\geq 3$ contains a cycle of length $2^k$ for some $k\geq 2$. Suppose, for contradiction, that a counterexample exists, and let $G$ be a minimal counterexample: a graph with $\delta(G)\geq 3$ and no cycle of power-of-2 length, chosen with the fewest possible vertices, and — among those — the fewest possible edges.

Question Carr answers: what must the *degree distribution* of any such $G$ look like? Specifically — must $G$ be "close to" 3-regular (cubic), or could it be dominated by high-degree vertices?

Facts

- Prior structural fact (K. Markström, 2004), the base this result builds on: any minimal counterexample must contain *both* a vertex of degree exactly 3 and a vertex of degree $\geq 4$ (arxiv.org/abs/2605.22844, citing [Ma04]; also independently listed in this wiki's /erdos/wiki/problems/64.md). - Computational context: Markström's exhaustive search shows any *cubic* counterexample needs $\geq 30$ vertices; Royle showed any counterexample at all needs $\geq 17$ vertices (per erdosproblems.com/64 comment thread, cross-cited in arxiv.org/abs/2605.22844). - Carr had already produced a partial-case win on this conjecture: "Cycles of Length 4 or 8 in Graphs with Diameter 2 and Minimum Degree at Least 3," arXiv:2508.19302 (Aug 2025) — a restricted-class (diameter-2) confirmation, distinct from and prior to this structural paper. - This paper (arXiv:2605.22844, submitted 13 May 2026) is a short, 4-page structural result — not a resolution of the Erdős–Gyárfás conjecture itself, which remains open (Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle).

Solution

Answer: Let $G$ be any minimal counterexample to the Erdős–Gyárfás conjecture, let $n_3$ be its number of degree-3 vertices and $n_{\geq4}$ its number of degree-$\geq4$ vertices ($n=n_3+n_{\geq4}$). Then:

1. The degree-$\geq4$ vertices form an independent set (Carr, Cor. 0.1(2)). 2. Every vertex of $G$ is adjacent to a degree-3 vertex (Carr, Cor. 0.1(1)) — an immediate consequence of (1). 3. At least $4/7$ of the vertices of $G$ have degree exactly 3: $n_3 \geq \tfrac{4}{7}n$ (Carr, Thm 0.1). This is the sense in which $G$ is "predominantly cubic." 4. Corollary: any *regular* minimal counterexample must be exactly 3-regular (cubic) — a regular graph with $n_{\geq4}=n$ would force the whole vertex set to be independent by (1), contradicting $\delta(G)\geq 3 > 0$ edges.

**The transferable technique — turn "minimality" into a hard *degree-counting* constraint via the standard edge-deletion argument, then close with a one-line double-counting inequality:**

1. Minimal-counterexample setup. Assume $G$ is a smallest-order, then smallest-size, graph with $\delta(G)\geq3$ and no power-of-2 cycle. This is the classical "minimal counterexample" proof schema (used throughout extremal graph theory): any proper reduction of $G$ that still satisfies the hypothesis ($\delta \geq 3$) must, by minimality, contain the desired structure (a power-of-2 cycle) — and since the reduction is a subgraph of $G$, that cycle survives in $G$ too, contradicting that $G$ was a counterexample at all. This turns "no smaller bad graph exists" into a machine for ruling out local configurations.

2. Apply it to a single edge. Suppose two degree-$\geq4$ vertices $u,v$ are adjacent. Delete the edge $uv$. Both endpoints still have degree $\geq3$ after the deletion (since they started at $\geq4$), so $G-uv$ still satisfies $\delta\geq3$, has the same order but strictly fewer edges than $G$. By edge-minimality of $G$, $G-uv$ is *not* a counterexample, so it contains a power-of-2 cycle — which, being a subgraph of $G-uv\subseteq G$, is also a cycle of $G$. But $G$ has no power-of-2 cycle by hypothesis — contradiction. Hence no two degree-$\geq4$ vertices can be adjacent: they form an independent set. This single move (delete one edge, invoke minimality, get a contradiction) is the entire engine of the paper; it is applied once to get the independent-set structural fact, and the rest is arithmetic.

3. Convert the structural fact into a counting bound via a cut argument. Because $V_{\geq4}$ is independent, *every* edge incident to a degree-$\geq4$ vertex has its other endpoint in $V_3$ (the degree-3 vertices) — there is no way for a degree-$\geq4$ vertex to "waste" an edge on another high-degree vertex. Counting the edge cut $E(V_3,V_{\geq4})$ from both sides: - From the $V_{\geq4}$ side: each of the $n_{\geq4}$ vertices contributes $\geq4$ edges, all landing in $V_3$, so $|E(V_3,V_{\geq4})| \geq 4\,n_{\geq4}$. - From the $V_3$ side: each of the $n_3$ vertices has degree exactly 3 total, so it can contribute *at most* 3 edges to this cut, giving $|E(V_3,V_{\geq4})| \leq 3\,n_3$. - Combining: $4n_{\geq4} \leq 3n_3$. Substituting $n_{\geq4}=n-n_3$ and solving gives $4n \leq 7n_3$, i.e. $n_3 \geq \tfrac47 n$.

4. Why this is the reusable idea. The technique is not specific to power-of-2 cycles at all — it is a **general two-step recipe for pruning the search space of a minimal counterexample to *any* minimum-degree-type extremal conjecture**: (a) use one-edge (or one-vertex) deletion plus minimality to force a purely *local* structural constraint (here: no two high-degree vertices touch) — this step only needs the hypothesis to be monotone-preserving under the deletion (min degree stays $\geq$ the threshold); (b) feed that local constraint into a *global* double-counting/cut inequality between the "boundary" degree class and the rest, which mechanically produces a quantitative density bound. This is exactly the same two-step shape as classical discharging arguments in graph coloring (local reconfiguration rule $\to$ global charge-counting contradiction), but here it is cheap enough to run without a discharging scheme at all — a single edge-cut inequality suffices. Any open problem phrased as "does every graph with $\delta(G)\geq d$ satisfying [property] contain [structure]" is a candidate for this same pruning move: it won't solve the conjecture, but it shrinks the space any exhaustive/SAT search or further structural argument has to cover — which is precisely how this wiki's /erdos/wiki/problems/64.md page uses it, to justify restricting nauty/geng exhaustive search to near-cubic graphs.

Related

- Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — the Erdős–Gyárfás conjecture itself (open); this result is a structural pruning lemma on the space of hypothetical counterexamples, not a resolution — it narrows, but does not close, the search. - Structural constraints on a hypothetical minimal counterexample (minimum-degree, connectivity, adjacency pruning) — the general edge/vertex-deletion-plus-minimality proof schema this paper instantiates; also referenced from /erdos/wiki/problems/64.md. - Discharging method — charge-counting technique for planar/structural graph coloring and cycle-existence proofs — the closest classical cousin: local reconfiguration rule -> global counting contradiction, same two-step shape as steps 2-3 above, used e.g. by Heckman & Krakovski (2013) on the 3-connected cubic planar case of the same conjecture. - nauty/geng/plantri: canonical-construction-path exhaustive generation of graphs (min-degree / cubic / planar families) — the exhaustive-search tool this result directly feeds: Carr's $4/7$-cubic + "every vertex touches a degree-3 vertex" constraints let a geng -d3 -D3-style search prune the candidate space for future computational attacks on Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle.