Erdős–Gyárfás conjecture confirmed for 3-connected cubic planar graphs (Heckman–Krakovski 2013)

Statement

The Erdős–Gyárfás conjecture (1995) states: every graph of minimum degree at least 3 contains a simple cycle of length $2^m$ for some integer $m \ge 2$ (a cycle of length 4, 8, 16, 32, ...). It is open in general — Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle.

Heckman and Krakovski prove the conjecture for the restricted class of 3-connected cubic planar graphs:

> Theorem 1.1. Every 3-connected cubic planar graph contains a $2^m$-cycle, for some $2 \le m \le 7$ (i.e. a cycle of length 4, 8, 16, 32, 64, or 128).

They note it is *not clear the bound $m\le7$ is tight* — possibly $2\le m\le4$ already suffices, but their method only delivers $m\le7$. As a corollary (1.2) they get a structural/algorithmic bonus: there is an absolute constant $c$ such that every 3-connected cubic plane graph has a face $f$ with $|f|\le71$ and a bounded subgraph $H$ ($|V(H)|\le c$, every vertex within path-distance 6 of $f$) containing the witnessing $2^m$-cycle — which yields a linear-time algorithm to find it.

Facts

- Venue: Christopher Carl Heckman (Arizona State Univ.) & Roi Krakovski (Ben-Gurion Univ.), "Erdős-Gyárfás Conjecture for Cubic Planar Graphs," *Electronic Journal of Combinatorics* 20(2) (2013), #P7. Submitted 23 May 2011; accepted 30 Mar 2013; published 9 Apr 2013. - Prior state going in: by computer search, Markström (2004) had verified the full conjecture for all cubic graphs of order $\le29$, and found the smallest cubic *planar* graph with no 4- or 8-cycle has 24 vertices — but that graph does contain a 16-cycle, so it is not a counterexample to the conjecture, only to a naive "$m\le3$" strengthening. Shauger (2004) had proved the conjecture for $K_{1,m}$-free graphs of min degree $\ge m+1$ or max degree $\ge2m-1$; Daniel & Shauger (2001) had proved it for *planar claw-free* graphs. Heckman–Krakovski's is the first result covering all 3-connected cubic planar graphs, claw-free or not. - Scope, precisely: requires both 3-connectivity *and* planarity *and* exact cubicity (every vertex degree exactly 3) — the general min-degree-$\ge3$ Erdős–Gyárfás conjecture remains open, Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle. - The proof is a proof by contradiction on a minimal counterexample, is long (43 pages), and is explicitly described by the authors as "computer-based in parts." - Related problems already in this wiki: Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle (the open general conjecture this proves a special case of; erdos/64.md already lists this paper as reference [HeKr13] among the confirmed restricted classes), Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often (chromatic-number analogue, solved by an unrelated technique — sublinear expanders, see Erdős–Gyárfás conjecture confirmed for 3-connected cubic planar graphs (Heckman–Krakovski 2013) vs that page for contrast), Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree) (Erdős–Hajnal reciprocal-sum sibling).

Solution

Answer: yes, for 3-connected cubic planar graphs. The proof technique — the transferable part — is a discharging argument whose per-face charge bound is not hand-verified but computed by solving a family of small integer linear programs, layered on top of a combinatorial "cluster" decomposition. This is a genuine methodological innovation over classical discharging (e.g. the Four Color Theorem's use of it): instead of manually enumerating and checking finitely many "reducible configurations," the authors reduce the hard part of the case analysis to *optimization problems* that a computer solves exactly.

1. Setup — charges from Euler's formula. For a 3-connected cubic plane graph $G$, assign initial charge $ch(v)=4-\deg(v)$ to every vertex (so every vertex, being cubic, starts with charge $+1$) and $ch(f)=4-|f|$ to every face. Euler's formula gives $\sum_v ch(v) + \sum_f ch(f) = 8 > 0$ (Lemma 5.1). The goal, standard to discharging, is to redistribute charge locally (15 explicit Rules, e.g. "a $(\ge11,\ge11,\ge11)$-face sends $\frac13$ to each adjacent face," "a $(3,\ge9,6)$-vertex sends $\frac13$ to its incident 6-face and $\frac23$ to its incident $\ge9$-face") so that after redistribution *every* vertex and face has modified charge $ch^*(x)\le0$ — which would force $\sum ch^* \le 0$, contradicting the invariant total of $8$. Since a real counterexample $G$ (no $2^m$-cycle for $2\le m\le7$) is assumed, showing this contradiction is always achievable proves no such $G$ exists.

2. The novel step — "clusters" turn the no-forbidden-cycle hypothesis into hard upper bounds on charge received. Around every face $f$, the authors build a maximal "almost pairwise disjoint" family $\Pi_f$ of local subgraphs ("clusters"), each isomorphic to one of a finite catalogue $\Im_{all}$ of combinatorial face-adjacency patterns (e.g. types denoted $(3)$, $(3,5)$, $(6,3,6)$, $(3,6,6,3)$...) and each sharing an edge with $f$. Because $G$ is assumed to contain no cycle of length $4,8,16,32,64,$ or $128$, the *number* of clusters of each type near $f$ is tightly constrained — e.g. two disjoint clusters whose face-boundary lengths sum in a certain way would together close up into a forbidden $2^m$-cycle, so that configuration cannot occur. This is where the "no forbidden cycle length" hypothesis — normally hard to use directly in a discharging framework — gets converted into concrete *counting inequalities* on cluster multiplicities $S_X = |\{c \in \Pi_f : c \text{ has type } X\}|$.

3. Bounding the charge a face can receive becomes an integer program, solved by computer. For each face size $|f|$ from 17 to 71 (larger/smaller faces are handled by separate, more direct arguments), the authors set up $$\text{maximize}\ total(f) \quad \text{subject to the cluster-counting inequalities derived in step 2 (plus problem-specific sub-case constraints)},$$ where $total(f)=\sum_{c\in\Pi_f} ch_f(c) + \tfrac13|V_s|$ is exactly the charge $f$ receives under the discharging Rules. They then show computationally that the IP's optimal value is always $\le |f|-4$, which is precisely what is needed for $ch^*(f)\le0$. Because there are 55 face sizes ($17,\dots,71$) times several sub-cases (splitting e.g. on whether $|S^{3/2}_{(3)}|\ge1$), this produces dozens of small integer programs, each mechanically solved rather than hand-checked — this is the "computer-based in parts" the abstract flags, and the "novel way" of applying the Discharging Method: replacing manual reducible-configuration case-checking with an ILP feasibility/optimality oracle over combinatorially-derived linear constraints.

4. Why the technique is transferable, and where it is known to break. The authors' own §6 ("Further Research") is explicit about the technique's reach: - Weakening planarity to projective-planarity looks feasible — the projective plane still has *positive* Euler characteristic, so the same discharging skeleton (total charge $>0$ forcing a positive-charge face) survives; the obstacle is that Section 2's topological lemmas (which rely on the Jordan-curve-style non-crossing structure of a plane embedding) would need reworking to tolerate the crossings projective-planarity allows. - Weakening 3-connectivity to 2-connectivity is flagged as the most promising direction — 3-connectivity was used only in a few places (the fact that any two faces share at most one edge, 1.3), so relaxing it mainly requires patching a bounded set of lemmas rather than redesigning the discharging rules. - Allowing degree-4 (non-cubic) vertices is flagged as the hardest generalization — it breaks the key structural fact "two faces sharing a vertex also share an edge," and would require re-deriving reducible configurations where negative-charge high-degree vertices force a nearby small forbidden structure rather than forbidding it outright. - This gives a concrete difficulty ordering for anyone trying to extend the min-degree-3 Erdős–Gyárfás conjecture toward more general graph classes: projective-planar cubic (easy-ish) < 2-connected cubic planar (promising) < higher-degree planar (hard) — a roadmap directly usable against Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle and its still-open neighbors.

Bottom line for downstream use: the "cluster + charge-bound-as-ILP" trick generalizes any discharging proof whose bottleneck is *proving a per-face/per-vertex charge bound too combinatorially intricate to case-check by hand* — instead of enumerating reducible configurations manually (classical style, e.g. Four Color Theorem), enumerate the finitely many *local combinatorial types* that can occur, derive linear counting constraints on their multiplicities from whatever global hypothesis is being contradicted (here: absence of specific cycle lengths), and let an integer/linear program certify the needed bound. This is a mechanizable, computer-checkable discharging pattern applicable wherever the forbidden substructure (cycle length, coloring obstruction, etc.) can be translated into linear inequalities on local configuration counts.

Related

- Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — the still-open general Erdős–Gyárfás conjecture (minimum degree $\ge3$, no planarity/cubicity/3-connectivity restriction); this paper is cited there as [HeKr13], one of several confirmed restricted-class results. - Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often — the chromatic-number analogue ("infinite chromatic number $\Rightarrow$ cycle of length $2^n$ infinitely often"), solved by an entirely different technique (sublinear expanders, Liu–Montgomery 2020) — useful contrast: two different $2^m$-cycle-forcing theorems solved by two structurally unrelated methods (expander embedding vs. discharging+ILP). - Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree) — Erdős–Hajnal cycle-length reciprocal-sum problem, sibling in the same cycle-length literature neighborhood. - Discharging method — charge-counting technique for planar/structural graph coloring and cycle-existence proofs — the base technique (charge assignment + local redistribution rules forcing a global contradiction via Euler's formula); this page is the concrete "novel" ILP-augmented instance of it, already referenced from erdos/64.md. - concept/reducible-configurations — the classical discharging notion of local structures forbidden in a minimal counterexample; here generalized to "clusters" whose *multiplicities* (not mere presence/absence) are bounded. - concept/computer-assisted-proof — the broader family of proofs (Four Color Theorem, Kepler conjecture, this paper) where a finite but too-large-for-hand-checking case analysis is discharged to a computer; here the mechanized step is integer-program optimality, not exhaustive case enumeration. - nauty/geng/plantri: canonical-construction-path exhaustive generation of graphs (min-degree / cubic / planar families) — Markström's (2004) exhaustive computer search establishing the pre-existing empirical lower bound (cubic counterexample needs $\ge30$ vertices; smallest cubic planar graph avoiding 4-/8-cycles has 24 vertices) that motivated and contextualized this theorem.