Mizzi’s conjecture on unstable graphs

Mizzi’s conjecture asserts that every nontrivially unstable graph, and every TF-cousin pair, contains circuits $C_k$ and $C_{2k}$ for some odd $k$. A related study had left the conjecture open after exhaustive verification through $9$ vertices.

Known results

• Exhaustive computation verified the circuit condition for connected graphs through $9$ vertices, including $469$ TF-cousin pairs on $9$ vertices; the conjecture was otherwise open.

August 2026 ten-vertex counterexample

Prateek R. Srivastava’s preprint gives a connected, nonbipartite, vertex-determining graph on ten vertices with simple-cycle lengths $5,5,6$. It has an explicit nontrivial two-fold automorphism, $(1\ 6)$ and $(2\ 3)$, proving instability, while it contains no required pair $C_k,C_{2k}$ for odd $k$; this claims the conjecture is false. The paper describes OpenAI Codex as assisting with development, verification, and drafting, while the author takes responsibility.

Current status (as of August 2026): Mizzi’s conjecture is claimed disproved by the ten-vertex preprint, but independent verification is not recorded, and related classifications remain open.