Computational research note · The Erdős–Gyárfás problem
Put some dots on a page and join them with lines however you like, under one rule: every dot must touch at least three lines. Now search your drawing for a round trip, a loop that walks along lines and returns to its start, whose length is exactly 4, or 8, or 16, or 32: a power of two.
Paul Erdős and András Gyárfás asked whether every such drawing must contain one of these loops. They believed the answer is no: that some clever tangle dodges every power of two at once. Nobody has found that tangle, and nobody has proved it impossible. What makes the problem unusual is how it would end. A single explicit drawing, checkable by a computer in seconds, would settle it forever. There is even prize money, though the sources disagree on how much (section 1).
This session went hunting for that drawing. Below is the closest thing anyone can put on a page: 24 dots, each touching exactly three lines, with no loop of length 4 and none of length 8 anywhere in it. Use the buttons to hunt its power-of-two loops yourself. Lengths 4 and 8 come up empty. Length 16 does not, and that is the whole story of why this graph is famous rather than immortal.
The state of play before this session, as far as we could verify it: computer searches credited to Royle and Markström had shown any counterexample needs at least 17 dots, and Klas Markström had exhaustively searched three-lines-per-dot ("cubic") drawings up to 28 dots back in 2004. One research session on four CPU cores, rebuilding everything from scratch with independently validated tools, produced three things.
Everything below is the technical version. Figure 2 is the wall of exhaustion behind the bound; figure 3 is the collapsing distance; both are drawn live from the committed numbers.
The Erdős–Gyárfás problem (erdosproblems.com #64) asks whether every finite graph with minimum degree at least 3 contains a cycle of length 2k for some k ≥ 2. Erdős and Gyárfás believed the answer to be negative; the modern "conjecture" is falsifiable by a single finite graph. We re-derive and extend the computational lower bounds on the order of a counterexample, from scratch and with independent tooling: nauty's geng, validated against OEIS; a purpose-built exact cycle-length checker, validated against networkx on 71 graphs; and a positive control the survivor filter must retain. Main new result: no graph with minimum degree ≥ 3 on at most 18 vertices is a counterexample (834,711,846 C4-free candidates scanned at n = 18 alone); the previously reported bound was 17 vertices (Royle and Markström, secondary-sourced). We also reproduce Markström's 2004 cubic censuses at order 24 clean-room, adding exact 16-cycle counts (330, 315, 207, 228; exactly one graph planar), and run simulated-annealing hunts for {4,8,16}-free cubic graphs in the window 54 ≤ n ≤ 62, the first orders where a cubic counterexample is possible at all and the obstruction set is exactly {4, 8, 16, 32}. Basin hopping reaches {4,8}-free cubic graphs on 56 vertices with 56 sixteen-cycles and on 58 vertices with 37; the minimum-C16 curve 207 → ≤ 56 → ≤ 37 falls steeply with order, and every extremal graph found is triangle-rich, girth 3, never high-girth.
Problem (Erdős–Gyárfás). Does every finite graph with minimum degree ≥ 3 contain a cycle of length 2k, k ≥ 2?
Erdős and Gyárfás believed the answer negative, and conjectured more strongly that no minimum-degree condition of any size forces a power-of-2 cycle. The strong form is false: Liu and Montgomery proved that sufficiently large minimum degree does force cycles of length 2k (a consequence of arXiv:2010.15802). The minimum-degree-3 question is untouched by that result and stands open. erdosproblems.com lists it as #64, status "falsifiable", with a $1000 prize; Wikipedia-derived snippets instead report $100 for a proof and $50 for a counterexample, and we could not resolve the discrepancy against Erdős's original problem papers this session.
A counterexample on n vertices must avoid cycles of every length 2k ≤ n. So it is C4-free by definition; on n ≤ 31 vertices the full obstruction set is {4, 8, 16}; from 33 to 63 vertices it is {4, 8, 16, 32}; past 64, a fifth forbidden length joins. Two structural facts focus the hunt on cubic (3-regular) graphs: sparser is easier (every extra edge is another way to close a bad cycle), and Carr proved in 2026 that every regular minimal counterexample is cubic, with at least 4/7 of the vertices of any minimal counterexample cubic (arXiv:2605.22844, secondary-sourced this session).
The prior computational frontier, all of it secondary-sourced this session (the sandbox could not reach arXiv, journals, or the authors' pages; see section 6):
| Known before this session | Due to | Status of our sourcing |
|---|---|---|
| No counterexample of any kind on ≤ 16 vertices ("at least 17") | Royle & Markström, computer search, apparently unpublished | secondary |
| All cubic graphs through order 28 exhausted; smallest {4,8}-free cubic graphs have order 24, and there are exactly four | Markström, Congr. Numer. 171 (2004) | secondary; census independently re-derived here |
| No cubic graph on ≤ 52 vertices avoids {4, 8, 16} | Markström, unpublished continuation | secondary |
| Smallest known cubic graphs avoiding {4,8,16} and {4,8,16,32}; the latter at order ≤ 450 | Exoo, arXiv:1403.5636 (2014) | secondary; construction orders unverified |
| Every 3-connected cubic planar graph has a 2m-cycle, m ≤ 7 | Heckman & Krakovski, Electron. J. Combin. 20(2) #P7 (2013) | secondary |
| Bipartite counterexamples need ≥ 32 vertices; cubic claw-free ones ≥ 114 | Nowbandegani & Esfandiari (2011; arXiv:1109.5398) | secondary |
| Claw-free and planar claw-free cases; various Cayley-graph families | Shauger (1998); Daniel & Shauger (2001); Ghaffari & Mostaghim (2018); Ghasemi & Varmazyar (2021) | secondary |
Since cubic graphs have even order, the consequence worth staring at: the first orders where a cubic counterexample can exist at all are n = 54, 56, 58, 60, 62, and on that whole window the price of admission holds steady at four forbidden lengths, {4, 8, 16, 32}. That window is where section 4 hunts.
Every graph with minimum degree ≥ 3 on at most 18 vertices contains a cycle of length 4 or 8. Consequently any counterexample to Erdős–Gyárfás has at least 19 vertices.
Since components of a minimum-degree-3 graph are themselves minimum-degree-3 graphs, it suffices to scan connected graphs; since a counterexample is C4-free by definition, it suffices to scan C4-free ones. geng -c -d3 -f generates exactly that class; every generated graph then had its 4- and 8-cycles tested by exact depth-first search (integer arithmetic only, C4-freeness re-verified per graph rather than trusted from the generator flag). None survived. Every single graph contains an 8-cycle:
| n | C4-free, min degree ≥ 3, connected | {4,8}-free found | Wall time | |
|---|---|---|---|---|
| 12 | 57 | 0 | seconds | |
| 13 | 503 | 0 | ||
| 14 | 6,059 | 0 | ||
| 15 | 91,433 | 0 | ||
| 16 | 1,655,659 | 0 | 37 s · 4 cores | |
| 17 | 34,758,006 | 0 | 599 s · 4 cores | New |
| 18 | 834,711,846 | 0 | 12,480 s · 3 cores · 48 work parts | New Certified |
One documentation hole in the session's certificate is closed here rather than there. The committed tables begin at n = 12, but the class is not empty below that: C4-free minimum-degree-3 graphs exist from n = 10 on (the Petersen graph is one of the five). While preparing this page, the bottom orders were scanned with an independent toolchain (Homebrew geng 2.9 plus a fresh DFS cycle checker, neither shared with the session): the class is empty for n ≤ 9, has exactly 5 graphs at n = 10 and 9 at n = 11, none of them {4,8}-free, and the overlapping orders 12…15 reproduce the session's counts to the digit. The sweep behind Theorem C1 is therefore complete from the very bottom.
Relation to prior work. The reported prior bound ("any counterexample has at least 17 vertices") is credited to Royle and Markström, known to us only through secondary sources, with the primary computation apparently unpublished. Theorem C1 is independent of that work and supersedes it by two orders. The next order, n = 19, needs roughly 2×1010 graphs by extrapolated growth: feasible but multi-day at this core count, and n = 20 wants 8-cycle pruning inside the generator (Markström-style) rather than brute force.
Among connected cubic graphs, no {4,8}-free graph exists with n ≤ 22 (C4-free counts scanned: 36 / 269 / 2,761 / 36,101 / 553,227 at n = 14 / 16 / 18 / 20 / 22). At n = 24 there are exactly four, among 9,467,449 C4-free cubic graphs: an independent clean-room reproduction of Markström (2004).
The cubic table's bottom orders close the same way as Theorem C1's: no C4-free cubic graphs exist at all for n ≤ 8, and the 3 at n = 10 and 8 at n = 12 all contain 8-cycles (scanned for this page with the independent toolchain of section 2, which also reproduces the session's counts at 14 ≤ n ≤ 20 exactly).
The characterization data is computed here and, as far as we know, partly new to the record: all four graphs have girth 3, their 16-cycle counts are 330, 315, 207 and 228, and exactly one is planar, the graph known as the Markström graph, drawn at the top of this page. In particular the minimum number of 16-cycles over all {4,8}-free cubic graphs on 24 vertices is exactly 207: the certified anchor of figure 3. The census also pins the bipartite side at this scale: no bipartite cubic {4,8}-free graph exists with n ≤ 26 (1,201 C4-free bipartite cubic graphs at n = 26, all containing 8-cycles).
The pleasant surprise of the session: hours before the census finished, the annealing search of section 4, started from a random cubic graph, converged at order 24 to a {4,8}-free graph. When the census landed, that graph proved isomorphic to the planar census graph. The search had rediscovered the Markström graph on its own. Beyond the poetry, this graph is the pipeline's positive control: a genuine survivor that the filter must retain end-to-end, guarding all the zero-survivor results above against silent false negatives. It passes (triple-verified: independent cycle enumeration, SAT unsatisfiability for C4 and C8, stability under random relabelings).
As a further sanity sweep, 23 named cubic graphs, built independently from their standard constructions (each self-certified for order, 3-regularity and girth before use), were all tested: every one contains a power-of-2 cycle. A selection, full table in the repository:
| Graph | n | Girth | Power-of-2 cycle lengths present |
|---|---|---|---|
| Petersen | 10 | 5 | 8 |
| Heawood | 14 | 6 | 8 |
| McGee | 24 | 7 | 8, 16 |
| Tutte–Coxeter | 30 | 8 | 8, 16 |
| Dyck | 32 | 6 | 8, 16, 32 |
| Harries | 70 | 10 | 16, 32, 64 |
| Foster | 90 | 10 | 16, 32, 64 |
| GP(48,7) | 96 | 8 | 8, 16, 32, 64 |
In the window n = 54…62 the session ran simulated annealing over connected cubic graphs: 2-edge-swap moves preserving 3-regularity and connectivity, with the energy an exact weighted count of 4-, 8- and 16-cycles (pruned DFS, no floating point in the counts; any zero-energy graph on ≤ 62 vertices would then face a single 32-cycle screen). Three escalations mattered. Focused moves: 70% of proposed swaps touch an edge lying on a currently-bad cycle, WalkSAT-style. Polish: a deterministic steepest descent over all ~13,000 possible 2-swaps, which proves the end state is a depth-1 local minimum. Basin hopping: anneal, polish, keep if better, repeat.
Chains at n = 54, 56, 58 and 60 all reach graphs with C4 = C16 = 0 and only three or four 8-cycles, pairwise vertex-disjoint, riding on triangles. Pinning the search to the {4,8}-free manifold instead and minimizing 16-cycles: at n = 56 the exact count fell 78 → 63 → 56 and then held for 60 fresh basin-hop rounds; at n = 58 a parallel descent reached 37, the session's best object.
No {4,8,16}-free graph was found, consistent with their scarcity (none exist below 54). A heuristic minimum bounds nothing; it measures search difficulty. But the certified 207 anchors the curve, and its steep fall is the most encouraging sign the session produced: the constraint visibly loosens with order, and the quantity is exactly the one a future session should keep pushing at n = 60 and 62, with a 32-cycle term in the endgame energy so that a zero-energy hit is a counterexample outright.
One structural observation held everywhere the session looked. Every extremal graph in sight is triangle-rich, girth 3: all four of Markström's order-24 graphs (the hero graph carries 7 triangles), and independently the annealer's records at n = 56 and 58 (16 and 17 triangles respectively), even though nothing in the energy rewards triangles. The stubborn last 8-cycles in the near-zero states sit almost entirely on triangle clusters. High girth, the natural-looking tool for killing short cycles, never once produced a winner.
A plausible reading: triangle-rich graphs have "elastic" cycle spectra, in which the same global circuit realizes several nearby lengths and local surgery tunes them, one unit at a time, to straddle 4, 8, 16, 32. High-girth graphs are the opposite: rigid, with their short spectrum out of the optimizer's control. The smallest girth-9 cubic graphs, the eighteen (3,9)-cages, have 58 vertices, inside the critical window, and girth 9 already kills lengths 4 and 8 by construction; only 16- and 32-cycles stand between any of them and a counterexample. No published screen of the cages for C16 and C32 could be found, the data was unreachable from the session's sandbox, and it goes down as the sharpest open thread rather than a result.