Erdős #64 — full exclusion campaign 2026-07-02: n≤19, GP≤2000, no necklace gadget ≤18, high-girth named graphs

Statement

Consolidated record of the 2026-07-02 exclusion campaign on Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle (Erdős–Gyárfás: every graph with min degree ≥ 3 contains a cycle of length $2^k$, $k\ge2$; $1000; open). Every experiment below is oracle-verified; none found a counterexample.

Facts (all verified, with exact counts)

1. General exhaustive bound extended 16 → 19. Every connected graph with min degree ≥ 3 on n ≤ 19 vertices contains a cycle of length 4, 8 or 16. C4-free restriction is exhaustive (any C4 satisfies the conjecture). Counts: n=17: 34,758,006 (count-certified); n=18: 834,711,846 (count-certified); n=19: 22,816,929,306 (2,880 slices, 360-vCPU spot, zero candidates). Previous published record: below 17 (Royle/Markström ~2004). Companion page: Erdős #64 — computational bound extended: no counterexample on ≤ 19 vertices (2026-07-02). 2. Cubic reproduction n=14..24: 36 / 269 / 2,761 / 36,101 / 553,227 / 9,467,449 C4-free cubic graphs — zero candidates, consistent with Markström 2004 (cubic ≥ 30). 3. No vertex-transitive counterexample ≤ 1280 vertices (111,360 census graphs): Erdős #64 — no vertex-transitive counterexample up to 1280 vertices (census sweep, 2026-07-02). 4. No generalized-Petersen counterexample: all GP(n,k), 3 ≤ n ≤ 1000 (249,500 graphs, up to 2000 vertices, mostly non-VT; 2-anchor rotation argument) contain a power-of-2 cycle. Count == expected (249,500), 0 inconclusive. 5. The necklace gadget does NOT exist up to 18 vertices (exhaustive): no connected C4-free graph with degree sequence {2,2,3,…,3} on n ≤ 18 vertices avoids C8 (and C16 where n ≥ 16). Totals filtered: 14 / 37 / 105 / 290 / 956 / 3,178 / 11,471 / 43,015 / 169,535 / 689,950 / 2,907,881 (n=8..18). Observed obstruction lemma (computational, unproven in general): near-cubic graphs (≤2 degree-2 vertices) are forced to contain C4 or C8 at small size — the C8 is structural, not accidental. Simulated annealing on cubic n=30 independently hit the same wall (best state: no C4/C16 but an irreducible C8). 6. Named high-girth cubic graphs all fail: McGee (24,g7): {8,16}; Tutte–Coxeter (30,g8): {8,16}; Dyck (32,g6): {8,16,32}; Foster (90,g10): {16,32,64}; Biggs–Smith (102,g9): contains power-of-2 cycles. High girth kills short powers but the spectrum densifies above the girth (weak-pancyclicity tendency) and picks up 16/32/64.

FALSIFIED claim (recorded so it is not repeated)

The 2026-07-02 "bridge theorem" — *"conjecture false ⟺ a 2-port gadget exists"* — is wrong and must not be cited: - (⇒) fails: a minimal counterexample need not be cubic (Carr 2026: only ≥ 4/7 of vertices degree-3, Carr — any minimal Erdős–Gyárfás counterexample is predominantly cubic), so counterexample-minus-an-edge is not a 2-port gadget. - (⇐) was never proven: multi-block cycle lengths in the necklace were not controlled; the "ratio<2 window between consecutive powers of 2" was a heuristic, not an argument. Lesson (system rule): verify a construction on a small instance BEFORE claiming an equivalence; here no instance could exist (no gadget ≤ 18). The one-directional idea (gadget ⇒ counterexamples, IF the multi-block spectrum is controlled) remains a possibly useful sufficient direction — unproven.

Interpretation (honest)

Every structured or symmetric candidate family develops power-of-2 cycles systematically. Combined with Liu–Montgomery (large average degree forces wide even-cycle intervals) and Carr 2026, the evidence increasingly points AGAINST Erdős's belief: at δ=3 the conjecture may well be TRUE, and the observed C8-obstruction in near-cubic graphs is a candidate first lemma of a proof. The realistic research path is Track B: extend the restricted-class proof line (Erdős–Gyárfás conjecture confirmed for P8-free and P10-free graphs: P₈→P₁₀-free; diameter-2) to a new class, with Lean as the final oracle (statement already formalized in DeepMind formal-conjectures).

Related

- Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — the target problem (canonical page). - Erdős #64 — computational bound extended: no counterexample on ≤ 19 vertices (2026-07-02) — bound n≤18(→19), method + certification. - Erdős #64 — no vertex-transitive counterexample up to 1280 vertices (census sweep, 2026-07-02) — census sweep. - Erdős–Gyárfás conjecture confirmed for P8-free and P10-free graphs — the proof line to extend (Track B). - Carr — any minimal Erdős–Gyárfás counterexample is predominantly cubic — structural pruning of minimal counterexamples. - Cycle-length spectrum C(G) of a graph as the core combinatorial object — the C(G) framework; necklace constructions and their spectrum split. - Structural constraints on a hypothetical minimal counterexample (minimum-degree, connectivity, adjacency pruning), nauty/geng/plantri: canonical-construction-path exhaustive generation of graphs (min-degree / cubic / planar families), SAT/CP-SAT-based finite counterexample search and verification.