The Tutte Graph is three-regular, planar, non-hamiltonian and three-connected!
Three-regular
Every vertex (the blue points) has three neighbours (connected by lines, called edges)
Planar
The edges can be drawn in the plane without crossing each other.
Non-hamiltonian
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.
Three-connected
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. <
Statistics
- 46 vertices
- 69 edges
- 25 faces
Check Euler’s formula (V – E + F = 2):Â 46 – 69 + 25 = -23 + 25 = 2
History
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.
