Tutte's graph was/is a famous counterexample to Tait's conjecture that every cubic, polyhedral graph has a Hamiltonian cycle. However, I cannot get access to Tutte's original paper (it's stuck behind an academic pay-wall which as a pre-university student I can't get past) so I can't read the proof of it being a counterexample.
Could you link me to one or give one as an answer?
Best Answer
Tutte's 1946 paper, "On Hamiltonian circuits" (Journal of the London Mathematical Society, 21 (2), pp. 98–101), began with the pentagonal prism.
It is relatively easy to show that no Hamiltonian cycle in this graph can use both of the black edges. Now we bring in a lemma:
We replace two vertices incident to the black edges, on the same side of the prism, with triangles.
Suppose a Hamiltonian cycle of this graph uses a blue edge. By the lemma applied to the triangles, the cycle must use exactly one of the two other edges of the corresponding triangle, and hence the corresponding black edge. From here we see that no Hamiltonian cycle can use both of the blue edges.
Now replace the two blue edges by a small tree.
Any Hamiltonian cycle must use the black edge – if not, it uses the blue edges, but we have seen that this cannot be completed into a Hamiltonian cycle. We have circled one vertex, because the part of the graph outside this circle…
is a graph satisfying the requirements of the lemma. If the Hamiltonian cycle uses the blue linking edges, it would amount to a Hamiltonian cycle in the third graph in this answer, which is a contradiction, so any Hamiltonian cycle of any graph including this subgraph must use the black edge.
This is the Tutte fragment. The full Tutte graph places three such fragments with their black compulsory edges meeting at a point, with the blue edges connecting to each other:
Any Hamiltonian cycle must use the three black edges. This is absurd. Thus there are no Hamiltonian cycles in the Tutte graph, which is easily seen to be cubic and planar, completing the proof.