|
|
|
Every 3-connected cubic Graph (each Vertex has Valency 3) has a Hamiltonian Circuit. Proposed by Tait in 1880 and refuted by W. T. Tutte in 1946 with a counterexample, Tutte's Graph. If it had been true, it would have implied the Four-Color Theorem. A simpler counterexample was later given by Kozyrev and Grinberg.
See also Hamiltonian Circuit, Tutte's Graph, Vertex (Graph)
References
Honsberger, R. Mathematical Gems I. Washington, DC: Math. Assoc. Amer., pp. 82-89, 1973.