Erdős #64 — no vertex-transitive counterexample up to 1280 vertices (census sweep, 2026-07-02)

Statement

Every connected cubic vertex-transitive graph on at most 1280 vertices contains a cycle of length a power of two ($\geq 4$). Verified by exhaustive sweep of the complete Potočnik–Spiga–Verret census (111,360 graphs), 2026-07-02. Hence any counterexample to Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle (Erdős–Gyárfás) is either non-vertex-transitive or has more than 1280 vertices.

Facts

- Corpus: the COMPLETE census of cubic vertex-transitive graphs on ≤ 1280 vertices (Potočnik–Spiga–Verret, arXiv:1201.5317, J. Symb. Comput. 2013) — 111,360 graphs. - Result: 111,360/111,360 contain a power-of-2 cycle. 0 candidates, 0 inconclusive (per-graph DFS budget 10⁸ never exceeded — BFS-distance pruning was sufficient everywhere). - Strictly extends the known literature on symmetric classes, which covered only Cayley subfamilies: generalized quaternion / dihedral / semidihedral / order-$p^3$ groups [GhMo18], orders $2p^2$ and $4p$ [GhVa21] (see Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle Facts §restricted classes). Every Cayley graph is vertex-transitive, so this sweep subsumes those results up to 1280 vertices and covers the non-Cayley vertex-transitive graphs they could not reach. - Interpretation: combined with Carr 2026 ("minimal counterexamples are predominantly cubic but with degree-3/higher-degree mixing", arXiv:2605.22844), the counterexample — if it exists — is asymmetric: high symmetry forces short even cycles in practice. - Method note (soundness of the anchor trick): in a vertex-transitive graph, if any cycle of length L exists, its image under the automorphism group passes through vertex 0 — so anchoring the exact-length DFS at a single vertex is exhaustive. This is what makes L up to 1024 feasible (with BFS-distance pruning: prune any branch whose current vertex is farther from the anchor than the remaining steps). - Pipeline-integrity lesson (recorded): the census ships as sparse6, first sweep parsed graph6 → all graphs silently skipped; caught because the runner cross-reports graphs-checked vs expected (loud failure). Always certify checked-count == corpus-count.

Solution

Transferable technique: census-sweep with symmetry-anchored exact-length cycle oracle. When a conjecture's counterexample space intersects a fully-enumerated family (censuses: vertex-transitive, snarks, cages, House of Graphs), sweeping the census with a verified oracle is hours of compute for a definitive slice of the search space — far cheaper than generation. Anchor exact-length search at one vertex when vertex-transitivity holds; BFS-distance pruning makes long target lengths tractable on sparse graphs.

Related

- Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — the target problem; this eliminates the entire symmetric regime ≤ 1280. - Erdős #64 — computational bound extended: no counterexample on ≤ 19 vertices (2026-07-02) — companion result: no counterexample (of any symmetry) on ≤ 18 vertices; the two results bracket the search space from both ends. - nauty/geng/plantri: canonical-construction-path exhaustive generation of graphs (min-degree / cubic / planar families) — copyg format conversion; geng generation. - Structural constraints on a hypothetical minimal counterexample (minimum-degree, connectivity, adjacency pruning) — Carr 2026 pruning; supports the "asymmetric counterexample" reading.