Erdős #64 — computational bound extended: no counterexample on ≤ 19 vertices (2026-07-02)

Statement

Exhaustive computational verification for Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle (Erdős–Gyárfás conjecture: every graph with minimum degree ≥ 3 contains a cycle of length $2^k$, $k\geq 2$):

Every connected graph with minimum degree ≥ 3 on n ≤ 19 vertices contains a cycle of length 4, 8 or 16. Equivalently: any counterexample to Erdős #64 has ≥ 20 vertices.

This extends the previously published general bound (no counterexample below 17 vertices, Royle/Markström 2004 — see Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle Facts) by two vertex counts (17 and 18), verified 2026-07-02.

Facts

- Method: exhaustive generation of all connected C4-free graphs with min degree ≥ 3 (geng -q -c -d3 -f n, nauty 2.8.9) + cycle-length-spectrum oracle (does G contain a cycle of length exactly L for L ∈ {4, 8, 16}; C4-free restriction is exhaustive since any graph containing a C4 satisfies the conjecture trivially). - n = 17: 34,758,006 graphs — zero counterexamples (20 parallel slices, local 20-core). - n = 18: 834,711,846 graphs — zero counterexamples (1,440 slices, 360-vCPU c3d spot VM, ~4 minutes wall). - Count certification (n=18): independent geng -u enumeration = 834,711,846 = oracle-checked total. No graph lost in the pipeline. - Oracle verification: anchored-DFS exact-length cycle search, implemented twice (Python + C). Python validated against networkx.simple_cycles ground truth on all 1,241 atlas graphs (0 mismatches). C validated == Python on all 853 connected n=7 graphs and all 2,761 cubic C4-free n=18 graphs. The dual-oracle cross-check caught a real off-by-one bug in C v1 (closed cycles at length L−1) before any production run — recorded in negative memory. - Reproduction sanity: cubic C4-free n=14..22 (36 / 269 / 2,761 / 36,101 / 553,227 graphs) → 0 candidates, consistent with Markström 2004 (any cubic counterexample ≥ 30 vertices). - n = 19: 22,816,929,306 graphs — zero counterexamples (2,880/2,880 slices, 360-vCPU c3d spot). Bound: any counterexample has ≥ 20 vertices.

Solution

The transferable technique: generator/oracle separation with dual-implementation verification and independent count certification. (1) geng generates canonical non-isomorphic candidates restricted by necessary conditions of any counterexample (C4-free, min-degree); (2) an exact-length cycle oracle — validated against an independent ground truth AND a second implementation — filters; (3) geng -u certifies the pipe lost nothing. Slice-parallel (res/mod) → embarrassingly parallel, preemption-safe, resumable.

Related

- Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — the target problem ($1000, open); this page extends its Facts §computational bounds. - nauty/geng/plantri: canonical-construction-path exhaustive generation of graphs (min-degree / cubic / planar families) — the generator. - SAT/CP-SAT-based finite counterexample search and verification — alternative encoding for deeper n (not needed ≤ 19). - Structural constraints on a hypothetical minimal counterexample (minimum-degree, connectivity, adjacency pruning) — Carr 2026 pruning (arXiv:2605.22844), applies to cubic-focused deep runs.