Stephan WehnerBlog and Homepage

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.

Download for xfig

Download the xfig file.