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
The graph first appeared in a paper “On Hamiltonian Circuits” byÂ
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