Erdős #64 — unconditional 4-or-8 dichotomy ≤19, first C4+C8-free specimens (n=24), Pt-line ceiling at P17

Statement

Three verified results from the 2026-07-02/03 Track-B campaign on Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle:

1. Unconditional 4-or-8 dichotomy at small size. Every graph with minimum degree ≥ 3 on at most 19 vertices contains a cycle of length 4 or 8 (no need for 16). Exhaustive over all connected C4-free min-degree-3 graphs, filter = "no C8, C16 allowed": n=16: 1,655,659 → 0; n=18: 834,711,846 → 0; n=19: 22,816,929,306 → 0. (n=17 scan completing; n≤16 zero.) This is the SAME dichotomy the P_t-free line proves for restricted classes (Erdős–Gyárfás conjecture confirmed for P8-free and P10-free graphs) — but unconditional, at small n.

2. First known C4+C8-free min-degree-3 specimens (smallest known: 24 vertices). Simulated annealing (fitness = avoid {4,8} only) found three cubic connected graphs whose cycle spectrum skips exactly 4 and 8. Verified by two independent oracles. graph6 (reproducible in seconds): - n=24: W@O?G?_?O??d_O?EO?S??A@???a_A?_G??K_A_?OA_?C@C — spectrum {3,5,6,7,9..24}, induced-path max P17 - n=24: W?@C????D??_A??U?W??D?AAOAO@AAC?_o?A?a?@G_E?_? — spectrum {3,5,6,7,9..24}, induced-path max P17 - n=26: Y@?????OO??CA?Q?O?c@I?B?_CA_??G?C_??@g?G?B??gGW?A??k???` — spectrum {3,5,6,7,9..26}, induced-path max P19 All contain C16 (so they satisfy the conjecture; they are NOT counterexamples). First appearance of C4+C8-free min-deg-3 graphs is thus in n ∈ [20, 24]. Note: they have triangles (girth 3) — they dodge 4 and 8 without high girth.

3. Ceiling for the P_t-free proof line. The n=24 specimens have longest induced path P17, i.e. they are P₁₈-free. Hence *"P₁₈-free + δ≥3 ⇒ cycle of length 4 or 8" is FALSE* (explicit witness). The Gao–Shan → Hu–Shen → P₁₂/P₁₃ line (Erdős–Gyárfás conjecture confirmed for P8-free and P10-free graphs, current frontier P₁₃) can extend AT MOST to P₁₇ in its "4 or 8" form. Open gap for Track B: t = 14..17. For t ≥ 18 the correct target statement must include 16.

Facts

- Warm-start C16 irreducibility. 24 annealing runs seeded FROM the specimens (fitness = avoid {4,8,16}) all stalled at exactly "C16 present, C4/C8 absent" — the C16 never fell, mirroring how random-start runs at n=30 stalled at an irreducible C8. Pattern: eliminate 4 and 8, and 16 becomes the irreducible one. Combined with all exclusion results (Erdős #64 — full exclusion campaign 2026-07-02: n≤19, GP≤2000, no necklace gadget ≤18, high-girth named graphs), this is consistent evidence the conjecture is TRUE at δ=3. - Method notes: annealer = degree-preserving 2-edge-swaps + connectivity guard + Metropolis; exact-length oracle inside fitness validated against networkx (0 mismatch on all specimens produced); warm-start variant accepts a g6 seed. - These specimens are concrete anchor objects for a P₁₄-..P₁₇ proof attempt: any proof of "P_t ⇒ 4∨8" for t ≤ 17 must fail exactly on structures like these at t=18.

PRIOR ART CORRECTION (2026-07-03) — NOT novel

Our two 24-vertex witnesses are isomorphic to graphs already published by Hegde–Sandeep–Shashank in the special-graphs branch of their repo (github.com/rbsandeep/Erdos-Gyarfas): our witness #1 ≅ their 24-node-cubic-no-4-8-cycles-p18-free.3, witness #2 ≅ their .2 (verified by networkx.is_isomorphic). They have THREE such 24-node graphs (we reproduced 2), plus a 28-node P21-free graph, plus the Markström graph, plus a graph_test.py. Their branch README explicitly describes them as "24-node cubic P18-free graphs that do not have 4 to 8 cycles but contain 16 cycles."

⇒ The "P₁₇ ceiling" is THEIRS, not ours. These specimens and the P18-free observation are prior art. Do NOT claim them. Our search independently rediscovering them only validates our method — it is not a new result.

What is NOT in their repo and NOT done by them (per their paper, arXiv:2410.22842, which reports P14 ran out of memory): the exhaustive P14 proof ("no P14-free counterexample ⇒ 4-or-8 holds for t≤14"). That — our in-progress k=14 — is the only genuinely new step here, and it directly extends their work past their OOM barrier. Frame any outreach as building on them, crediting them, never as our discovery of the ceiling.

Related

- Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — target problem. - Erdős–Gyárfás conjecture confirmed for P8-free and P10-free graphs — the proof line this bounds from above. - Erdős #64 — full exclusion campaign 2026-07-02: n≤19, GP≤2000, no necklace gadget ≤18, high-girth named graphs — the full exclusion campaign. - Erdős #64 — computational bound extended: no counterexample on ≤ 19 vertices (2026-07-02) — general bound (≥20 vertices). - Cycle-length spectrum C(G) of a graph as the core combinatorial object — C(G) framework. - Simulated-annealing extremal search — Metropolis local search for rare, structured witness/counterexample objects — the search method.