Markström–Royle exhaustive computer search: lower bounds on Erdős–Gyárfás counterexamples

Statement

The Erdős–Gyárfás conjecture (Erdős & Gyárfás, 1995; Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle, prize \$1000/\$100 depending on citation; still open) asks: does every finite graph with minimum degree $\geq 3$ contain a simple cycle whose length is a power of 2 ($4, 8, 16, 32,\dots$)?

The full conjecture is not what this page reports as solved. What Klas Markström (building on an earlier search by Gordon Royle) settled by exhaustive computer search is a bounded, finite decision question that is fully computationally tractable and *does* have a definitive, verified answer:

> For each fixed graph class (general min-degree-3 graphs with the reduced minimal-counterexample degree structure; cubic graphs) and each fixed vertex count $n$ up to a feasible search limit, does a counterexample to the Erdős–Gyárfás conjecture exist on $n$ vertices?

This is a finite question — for each $n$ there are finitely many graphs, checkable by brute force — and Markström's 2004 paper (Congressus Numerantium 171, 179–192) answers it completely up to the largest $n$ his and Royle's computers could exhaustively enumerate, giving *rigorous, unconditional* lower bounds on the size of any hypothetical counterexample to the still-open full conjecture.

Facts

- Source: K. Markström, "Extremal graphs for some problems on cycles in graphs," *Congressus Numerantium* 171 (2004), 179–192 (§4, "Graphs with few cycles of length $2^k$"); read directly in full. This is also the paper cited as the sole reference for the computer-search bounds on erdosproblems.com's page for the conjecture. - **Structural pre-reduction used to shrink the search space (Markström 2004, predates and is reused by Carr's 2026 refinement, see Carr — any minimal Erdős–Gyárfás counterexample is predominantly cubic): if $G$ is an edge/vertex-minimal counterexample and $u,v$ both have degree $\geq 4$, then $\{u,v\}$ cannot be an edge — deleting it would leave both endpoints at degree $\geq 3$, giving a smaller counterexample by minimality, a contradiction. Hence any minimal counterexample decomposes as an independent set $V_1$ of degree-$\geq4$ vertices plus a nonempty set $V_2=V\setminus V_1$ of degree-exactly-3 vertices — quoted (with the italicized fact reconstructed from the PDF's own §4 argument). - General case (quoting the paper verbatim): "Using this observation Gordon Royle used a modified version of Brendan McKay's graph generator `makeg` to generate graphs without $C_4$'s and the described degree structure. Royle generated all relevant graphs on less than 16 vertices and found no counterexamples." This directly establishes any counterexample has $\geq 16$ vertices** from the print text alone; the figure now standard in the literature (erdosproblems.com, Wikipedia, and this wiki's Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle) is $\geq 17$ vertices, attributed jointly to "Royle and Markström" — one more vertex-level than the printed snapshot, almost certainly from Royle's own continuously-updated search page cited by Markström as [Roy]. - Cubic case, extended further (quoting the paper verbatim): "In order to extend this search further we choose to look at graphs with $V_1=\emptyset$, i.e. cubic graphs. We used Gunnar Brinkmann's cubic graph generator minibaum to generate all cubic graphs on less than 29 vertices and a simple fortran program to check for the existence of cycles of length 4, 8 and 16. No counterexamples to the conjecture was found." Since cubic (3-regular) graphs only exist at even order, "less than 29" already exhausts every candidate order up to the next possible one, 30 — so this establishes any cubic counterexample has $\geq 30$ vertices, the figure universally cited (erdosproblems.com, Wikipedia, arXiv:2605.22844). - The extremal near-miss objects found at $n=24$: "on 24 vertices we found the smallest cubic graphs without cycles of lengths 4 and 8. These graphs are displayed in Fig. 14. We note that the lower right of the four graphs can be constructed from $K_4$ by repeatedly expanding vertices into triangles, it is also the only planar graph among the four." I.e. $f(3)=24$ where $f(k)$ is the smallest order of a cubic graph with no $2^j$-cycle for $j\leq k$ — independently confirmed by a later paper ("Three Graphs and the Erdős-Gyárfás Conjecture," arXiv:1403.5636: "Markström [3] showed that $f(3)=24$, and listed all four minimal graphs"). Crucially, none of these four graphs is an actual counterexample to the conjecture — each still contains a $C_{16}$ (a power-of-2 cycle), just no $C_4$ or $C_8$; the well-known planar one of the four is now called the *Markström graph* (24 vertices, 36 edges, girth 3, cubic, planar, no $C_4$/$C_8$, but has $C_{16}$s). - A quantitative side table: Markström's Table 3 gives the exact count of connected cubic graphs with no $C_4$ and no $C_8$ at each order: $n=24$: 4 graphs; $n=26$: 23 graphs; $n=28$: 251 graphs — all still containing a $C_{16}$, hence none a counterexample. - Downstream reuse in this wiki: this exact search is what Erdős #64 — computational bound extended: no counterexample on ≤ 19 vertices (2026-07-02) (this wiki's own 2026 extension) explicitly builds on and cites as its baseline ("extends the previously published general bound... Royle/Markström 2004"), pushing the general-case bound from $\geq17$ to $\geq19$ vertices using the modern nauty/geng generator plus a dual-implementation cycle-length oracle — a direct, cross-verified, 20-years-later continuation of exactly the technique documented on this page.

Solution

Answer to the finite sub-question: as of the 2004 search, no counterexample to the Erdős–Gyárfás conjecture exists on $<17$ vertices in general, and none exists on $<30$ vertices among cubic graphs; the extremal graphs that come *closest* to being counterexamples (avoiding $C_4$ and $C_8$ simultaneously) first appear at exactly 24 vertices, all cubic, one of them planar (the Markström graph) — but every one of them still contains a $C_{16}$, so the full conjecture remains open. (The full conjecture is not resolved by this page's technique and is tracked separately at Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle.)

The transferable technique — the one that open problems in this wiki should borrow — is a three-part recipe for turning an infinite existence conjecture into a sequence of rigorous, mechanically-verified finite lower bounds:

1. Reduce the search space with a cheap structural pre-filter derived from minimality, before generating anything. Rather than generating *all* graphs with minimum degree $\geq 3$ at each order (astronomically many), Markström first proves a one-line structural fact about any *minimal* counterexample (no two degree-$\geq4$ vertices can be adjacent, by the standard "delete an edge, minimality forces a power-of-2 cycle to survive, contradiction" argument) and only generates graphs satisfying that reduced shape. This single move is what makes the general-case search at $n\sim16$ tractable, and pushing it to its logical extreme — restrict entirely to $V_1=\emptyset$, i.e. cubic graphs — is exactly what lets the *cubic* search reach $n=28$ (versus $n=15$/$16$ for the unrestricted case) with the same computational budget. The reusable move: before running any exhaustive search on a minimal-counterexample question, mine the minimality hypothesis itself for cheap local structural constraints (independent sets, forced degree patterns, forbidden adjacent configurations) and bake them into the generator, not just the checker. 2. Generate the reduced class isomorph-free, using a canonical-construction-path generator matched to the structural class. Two different purpose-built tools are used for the two structural regimes: Brendan McKay's makeg (the ancestor of today's geng, part of nauty) for the general min-degree-3-with-forbidden-$C_4$ class, and Gunnar Brinkmann's minibaum (ancestor of today's plantri/multig-style cubic generators) for cubic graphs specifically — because a generator specialized to a narrower class (e.g. regular graphs only) can reach far larger $n$ than a general-purpose one at the same cost. Both tools generate each graph up to isomorphism exactly once (no duplicate work, no missed graphs), which is what turns "we ran a big search and found nothing" into "we have exhaustively decided every graph of this order" — a mechanically checkable, reproducible completeness guarantee, not a heuristic sample. 3. Pair the generator with a cheap, separate necessary-condition oracle, and run it to exhaustion at each feasible order. A simple program (Markström used Fortran; the 2026 continuation in this wiki uses a dual C/Python implementation cross-validated against networkx.simple_cycles) checks each generated graph for the existence of cycles of the relevant power-of-two lengths ($4, 8, 16$ — the only lengths that can matter within the search's vertex-count ceiling). Any generated graph failing the check (i.e., missing all of $C_4, C_8, C_{16}$) is a genuine counterexample; finding none across an *exhaustively and completely enumerated* class at order $n$ is precisely what licenses the universal claim "any counterexample has $>n$ vertices" — a statement about *all* graphs, proved by checking finitely many, with no probabilistic or sampling gap. 4. Report both the negative result (a rigorous lower bound) and the near-extremal positive witnesses (structural insight for further attacks). The 24-vertex graphs that avoid $C_4$ and $C_8$ but still contain $C_{16}$ are not incidental output — they are the technique's second product: concrete, small, explicit examples showing exactly *how close* to a counterexample one can get, which is what seeds later structural work (e.g. Heckman–Krakovski's planar-cubic proof uses the Markström graph as a reference case; Carr's 2026 "predominantly cubic" pruning result explicitly cites and extends Markström's minimal-counterexample degree-structure lemma from step 1 above). 5. Why this transfers generically. Any Erdős-style "does structure $S$ force property $P$" conjecture that is (a) *finitely falsifiable* (a single finite counterexample would disprove it) and (b) admits *some* minimal-counterexample structural reduction, however weak, is a candidate for this exact recipe: mine minimality for a cheap pre-filter → hand the reduced class to the most specialized isomorph-free generator available for that class → run a fast, independently-validated necessary-condition oracle to exhaustion → report the resulting lower bound as a genuine, reproducible mathematical fact (not a heuristic), and keep the near-miss witnesses as a second, structurally informative output. This is exactly the recipe this wiki's own Erdős #64 — computational bound extended: no counterexample on ≤ 19 vertices (2026-07-02) page reruns twenty-two years later with modern hardware and tooling (nauty/geng in place of makeg, dual-oracle cross-validation, independent count-certification via geng -u) to push the same bound from 17 to 19 vertices, and it is the same recipe Carr — any minimal Erdős–Gyárfás counterexample is predominantly cubic strengthens on the *structural pre-filter* side (step 1) by proving a much sharper $4/7$-cubic density bound rather than just the qualitative independent-set fact.

Related

- Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — the Erdős–Gyárfás conjecture itself, still open; this page's exhaustive-search bounds are cited directly in its Facts section as the origin of the "computational lower bounds on any counterexample" line. - Erdős #64 — computational bound extended: no counterexample on ≤ 19 vertices (2026-07-02) — this wiki's own direct continuation of exactly this technique (same recipe, modern nauty/geng tooling, dual-oracle verification), extending the general-case bound from $\geq17$ to $\geq19$ vertices and independently reconfirming the $\geq30$-vertex cubic bound at intermediate orders as a sanity check. - Carr — any minimal Erdős–Gyárfás counterexample is predominantly cubic — sharpens exactly the step-1 structural pre-filter used here (independent set of degree-$\geq4$ vertices) into a quantitative $n_3\geq\tfrac47n$ density bound on any minimal counterexample, via the same one-edge-deletion-plus-minimality argument Markström used qualitatively in 2004. - Erdős–Gyárfás conjecture confirmed for P8-free and P10-free graphs — a structurally *different* (non-computational, forbidden-induced-path) route to confirming the conjecture on restricted graph classes; useful contrast showing exhaustive search and structural/case-analysis proof are complementary, not competing, attack modes on the same open conjecture. - nauty/geng/plantri: canonical-construction-path exhaustive generation of graphs (min-degree / cubic / planar families) — the geng/plantri/makeg/minibaum family of canonical-construction-path, isomorph-free graph generators that is the load-bearing tool of this page's technique. - Structural constraints on a hypothetical minimal counterexample (minimum-degree, connectivity, adjacency pruning) — the general "assume a smallest violating instance, derive local structural constraints via a one-edge/vertex-deletion argument" schema instantiated in step 1 above, and reused by essentially every other solved/open page in this wiki's Erdős–Gyárfás cluster. - SAT/CP-SAT-based finite counterexample search and verification — the modern alternative/complement to pure isomorph-free enumeration for pushing exhaustive bounds to even larger $n$ once generator-based enumeration becomes infeasible.