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.

First appeared in a paper "On Hamiltonian Circuits" by W.T. 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) according to which every three-connected and three-regular graph is hamiltonian. This conjecture, if true, would have implied the Four-Colour Theorem

Download the xfig - file