Fabian Arevalo

Computational research note · The Erdős–Gyárfás problem

Hunting the Erdős–Gyárfás counterexample

A certified 19-vertex lower bound for any counterexample, Markström's order-24 census re-derived clean-room, and record near-misses at 56 and 58 vertices.
July 30–31, 2026 · produced in a Claude Code research session (AI-assisted, disclosed) · code, data & graphs in the companion repository.

Start here — no maths required

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.

Hunt a loop of length
Counting loops in your browser…
The Markström graph, the smallest possible near-miss. 24 vertices, every one of degree 3, no 4-cycles, no 8-cycles: one of exactly four such cubic graphs at the smallest order where any exist, found by exhaustive census (section 3). The heavy loop is a 16-cycle, the reason it is not a counterexample. Nothing here is quoted from a file: your browser rebuilds the graph from its committed edge list, re-counts its 4-, 8- and 16-cycles, and finds the traced cycle itself, every time this page loads. The annealing search of section 4, started from a random graph and told nothing about the literature, converged to this exact graph on its own.

What this note adds

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.

  1. A new certified lower bound: 19 dots. We checked every drawing with up to 18 dots that could possibly work, 871,223,563 candidates at orders 12 through 18 alone, and every single one contains a loop of length 4 or 8. The previous bound, reported as 17, is superseded by two.
  2. An old census re-derived, and a rediscovery. At 24 dots there are exactly four cubic drawings dodging lengths 4 and 8. Markström found them in 2004; our independent pipeline finds the same four, never having read his files, and adds their 16-loop counts: 330, 315, 207 and 228. Better: our search algorithm, knowing nothing, converged to his most famous graph (the one above) entirely on its own. Not a new result, and we say so; it is the strongest validation the machinery could ask for.
  3. Record near-misses where a cubic counterexample could first exist. No cubic drawing on up to 52 dots dodges lengths 4, 8 and 16 (Markström again, unpublished). From 54 to 62 dots, dodging {4, 8, 16, 32} is the full price of a counterexample. Hunting there, simulated annealing produced a 56-dot drawing with no 4- or 8-loops and only 56 sixteen-loops, then a 58-dot drawing with only 37. At 24 dots the census forces 207. That number, the "distance to a counterexample", is collapsing as drawings grow. These are search records, not exhaustive minima, and the page labels them so.

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.

AbstractSummary of results

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.

Section 1The problem, and what a counterexample must look like

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 sessionDue toStatus of our sourcing
No counterexample of any kind on ≤ 16 vertices ("at least 17")Royle & Markström, computer search, apparently unpublishedsecondary
All cubic graphs through order 28 exhausted; smallest {4,8}-free cubic graphs have order 24, and there are exactly fourMarkström, Congr. Numer. 171 (2004)secondary; census independently re-derived here
No cubic graph on ≤ 52 vertices avoids {4, 8, 16}Markström, unpublished continuationsecondary
Smallest known cubic graphs avoiding {4,8,16} and {4,8,16,32}; the latter at order ≤ 450Exoo, arXiv:1403.5636 (2014)secondary; construction orders unverified
Every 3-connected cubic planar graph has a 2m-cycle, m ≤ 7Heckman & Krakovski, Electron. J. Combin. 20(2) #P7 (2013)secondary
Bipartite counterexamples need ≥ 32 vertices; cubic claw-free ones ≥ 114Nowbandegani & Esfandiari (2011; arXiv:1109.5398)secondary
Claw-free and planar claw-free cases; various Cayley-graph familiesShauger (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.

Section 2A new lower bound: 19 vertices

Theorem C1 · certified by exhaustion

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:

Hover a bar for the exact count.
The wall of exhaustion. Bars: how many connected C4-free graphs of minimum degree ≥ 3 exist at each order, on a log scale; these are all the places a counterexample could hide. Every bar was scanned to completion and the number of {4,8}-free survivors is the zero printed above the axis: measurement, from the committed count tables. The n = 19 bar is not a measurement: it extrapolates the observed ×21–24 growth per vertex, and marks the next target (roughly a multi-day run at this core count). Orders 10 and 11 (five and nine graphs, none surviving) are too small to plot on this scale; below 10 the class is empty. Both facts are re-verified in the text below.
nC4-free, min degree ≥ 3, connected{4,8}-free foundWall time
12570seconds
135030
146,0590
1591,4330
161,655,659037 s · 4 cores
1734,758,0060599 s · 4 coresNew
18834,711,846012,480 s · 3 cores · 48 work partsNew 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.

Section 3The order-24 census, re-derived, and a rediscovery

Proposition C2 · certified by exhaustion

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:

GraphnGirthPower-of-2 cycle lengths present
Petersen1058
Heawood1468
McGee2478, 16
Tutte–Coxeter3088, 16
Dyck3268, 16, 32
Harries701016, 32, 64
Foster901016, 32, 64
GP(48,7)9688, 16, 32, 64

Section 4The hunt in the window

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.

min #C16, {4,8}-free cubic
207 (n = 24, exact)  →  ≤ 56 (n = 56)  →  ≤ 37 (n = 58)
Both record graphs are committed in graph6 form and verified three independent ways: networkx cycle enumeration, SAT unsatisfiability for C4 and C8, stability under 10 random relabelings. Spectra {16, 32}. Verified again with networkx 3.5 on a second machine while preparing this page.
Hover a point for its provenance.
The distance to a counterexample, measured in 16-cycles. Each point is the smallest number of 16-cycles in any known {4,8}-free cubic graph of that order. The three points carry three different strengths of claim, and the markers say so: the filled square at n = 24 is an exact minimum over the full census (certified); the hollow squares at 56 and 58 are the best graphs a heuristic search found, upper bounds on an unknown minimum (the arrows point at where the truth could still be). The dotted polyline is a guide for the eye, not a fit. No {4,8}-free cubic graphs exist at all below n = 24, and no cubic graph below n = 54 reaches zero (Markström's unpublished exhaustion, secondary-sourced). Zero anywhere in the shaded window leaves exactly one 32-cycle check between that graph and the conjecture.

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.

Section 5Why triangles win (a mechanism, not a theorem)

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.

Loop length before
Why triangle surgery gives fine control over loop lengths. A loop of length L runs through one corner of a graph (the corner's third edge dangles off to the rest of the graph, faint). Expanding that corner into a triangle (a Y→Δ move) forces the loop to cross the new triangle, and there are two ways across: the short side (length L+1) or the long way around (length L+2). Both now exist in the graph. So triangle moves shift cycle lengths in steps of one or two, which is exactly the fine motor control an optimizer needs to steer lengths between the powers of two; try length 14 or 15 before expanding and watch a forbidden 16-loop appear. This is a heuristic mechanism read off the extremal graphs, not a theorem, and the caption of every girth-based dead end in the session says the complementary thing: high girth rigidifies the short spectrum instead.

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.

Section 6What is certified, what is not

Certified (exact, reproducible, integer-only)

Numerical (evidence, not proof)

Secondary-sourced (flagged, awaiting primary verification)

Section 7Open threads

  1. Push the general bound past 19: n = 19 is ~2×1010 C4-free graphs (multi-day at four cores), and n = 20 wants generation-time 8-cycle pruning à la Markström's modified minibaum.
  2. Drive the C16 curve at n = 60 and 62 below 37, and to zero if it will go; add a 32-cycle existence term to the endgame energy so a zero-energy hit is a counterexample outright.
  3. Screen the eighteen (3,9)-cages (58 vertices, girth 9, so no C4 or C8 by construction) for 16- and 32-cycles. No such screen appears to be published. Two absences in any one of them would end the conjecture.
  4. Verify every secondary-sourced literature claim against primary sources; resolve the prize discrepancy ($1000 vs $100/$50) against Erdős's original problem papers.
  5. Find any {4,8,16}-free cubic graph on 54…62 vertices, or push annealing evidence that none exists there either.