The Tutte Graph is three-regular, planar, non-hamiltonian and three-connected!
Every vertex (the blue points) has three neighbours (connected by lines, called edges)
The edges can be drawn in the plane without crossing each other.
There is no hamiltonian circuit: an ordering of the vertices so that each two vertices in the sequence are connected and the first vertex is connected to the last vertex in this ordering.
Removing any two vertices leaves the graph connected (there is a path between each two vertices). But removing three vertices may result in a disconnected graph. <
- 46 vertices
- 69 edges
- 25 faces
Check Euler’s formula (V – E + F = 2):Â 46 – 69 + 25 = -23 + 25 = 2
The graph first appeared in a paper “On Hamiltonian Circuits” byÂ William Thomas Tutte, in the Journal of the London Mathematical Society, vol. 21, p. 98-101, in 1946.
It refuted a conjecture by P.G. Tait (see “Remarks on the Colouring of Maps” in the Proceedings of the Royal Society of Edinburgh, vol. 10, p. 729, 1880, or at wikipedia) according to which every three-connected and three-regular graph is hamiltonian.
This conjecture, if true, would have implied the Four-Colour Theorem. Other counterexamples are compiled at MathWorld.