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

Abstract

A graph G is said to be maximal non-Hamiltonian if G is non-Hamiltonian, but $G+e$ is Hamiltonian for every nonedge $e$ of $G.$ In 1994, Vu Dinh Hoa conjectured that if $C$ is a longest cycle of a maximal non-Hamiltonian graph $G,$ then $G-V(C)$ is a complete graph. We disprove this conjecture by constructing a counterexample of every order $n\ge 56.$ We also pose several related open problems.

Disclosure

“ere exist a maximal non-Hamiltonian graph G of order n and a longest cycle C of G such that G − V (C) has exactly k components. Determine f (n). The results of this paper show that f (n) ≥ 2 for every n ≥ 56. Declaration of AI Use ChatGPT was used to assist in developing and checking the constructions and proofs. The author independently verified all mathematical arguments, wrote the paper, and takes full responsibility for its content. Acknowledgements. This research”

PDF page 8

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T19:17:11.201214Z

Structural counts