The Erdős–Gyárfás Conjecture for Cubic Graphs of Order 30

Abstract

This record contains the preprint and complete reproducibility archive for a computer-assisted proof that every connected cubic graph on 30 vertices contains a cycle of length 4, 8, or 16. The proof partitions a hypothetical counterexample by its exact number of triangles, t = 0, …, 10. For t ≥ 1, the disjoint triangles are contracted to protected marks, and an exact cycle-lift law converts the problem into finite marked-cycle conditions. All eleven strata are eliminated by exhaustive deterministic searches using independent verification implementations. The evidence is preserved in a SHA-256-sealed dependency chain and includes a successful complete replay on a second physical machine. Scope: this work establishes the order-30 cubic case only. The unrestricted Erdős–Gyárfás conjecture remains open. The corollary that a cubic counterexample must have at least 32 vertices explicitly depends on Markström’s external exhaustive verification of smaller cubic orders; that external computation is not re-certified here. Files deposited separately are the principal paper PDF and the complete final submission and reproducibility packet. SHA-256 of paper_octave_order30.pdf: 181a479f31b31feaa0803a92479b6f80228f8780def5d958e628cea00dfd1758. SHA-256 of OCTAVE_ORDER30_FINAL_SUBMISSION_AND_DEPOSIT_PACKET_V1.zip: 09920b7f3d098c6b0e09fb6ff4ad44de815518eeebc51562679ea654112619ee.