Hoa's Conjecture on Maximal Non-Hamiltonian Graphs

A graph $G$ is maximal non-Hamiltonian if it is non-Hamiltonian but $G + e$ is Hamiltonian for every nonedge $e$ . In 1994 Vu Dinh Hoa conjectured a property of $G - V(C)$ for a longest cycle $C$ of such a graph. Disproved by an explicit base graph on 56 vertices, extended to larger orders.

Result: Disproved
Status: Resolved
AI contribution: AI co-developed
Method: Construction
Field: Graph theory
Posed by: Vu Dinh Hoa
Year posed: 1994
Years open: 32y
Solved: 2026-08-02
Model: ChatGPT
Vendor: OpenAI
Collaborators: Xingzhi Zhan
Verification: Unreviewed
Publication: Preprint
Significance: 10 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What the AI did

The declaration of AI use says ChatGPT assisted in developing and checking the constructions and proofs, with the author independently verifying all arguments.

Verification

arXiv preprint, not yet peer-reviewed.

Source

arXiv:2608.00957 - Counterexamples to a conjecture of Hoa on maximal non-Hamiltonian graphs

Hoa's Conjecture on Maximal Non-Hamiltonian Graphs

What the AI did

Verification

Source

Discussion