1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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:

In a connected graph, if there is a subgraph linked to the rest of the graph by exactly three edges, any Hamiltonian cycle of the whole graph uses exactly two of the linking edges. In particular, the subgraph can be shrunk to a point while preserving Hamiltonian cycles.

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.

$\endgroup$
  • $\begingroup$ Is it possible to link to a proof of the lemma? $\endgroup$ – Isky Mathews Oct 31 '18 at 16:49
  • 1
    $\begingroup$ @IskyMathews It's very easy to show, by considering cases. Parity rules out an odd number of linking edges used, and obviously we can't have zero linking edges used, so there must be two. Tutte omitted the proof in the actual paper. $\endgroup$ – Parcly Taxel Oct 31 '18 at 16:52
3
$\begingroup$

This is actually fairly quick to see by exhaustive search -- the greatest trouble is to bite down and decide to start an exhaustive search.

Because the graph is cubic, finding a Hamiltonian cycle corresponds to coloring all of the edges red or green such that

  • each vertex is incident to exactly two red edges and one green edge.
  • there is no cycle of red edges that touch fewer than all of the vertices.

This means that as you assign colors, you can follow these rules

  1. Whenever you color an edge green immediately color all of its four neighbors red.

  2. Whenever two neighor edges are colored red, color the third edge from the vertex they share green.

  3. If coloring an edge red would create a small red cycle, immediately color it green.

These rules mean that a lot of decisions are forced for you. Start by deciding which of the edges incident to the middle node are red and green. It doesn't matter what you choose at this point, since the graph is symmetric around this node. Immediately following the rules above, we arrive at this situation:

first step of coloring

Work now only in the bottom Tutte fragment. The links to the two other fragments certainly will need to be in our Hamiltonian cycle:

second step of coloring

But now we have a choice. Let's proceed by case analysis on where the cycle continues at the vertex marked by an arrow. For example suppose it goes left. Quite a lot of colors are then forced one by one:

one branch of the case analysis

And now we're painted ourselves into a corner, because the next application of rule 1 will create a small red cycle. This branch of the case analysis is impossible!

Going down goes only slightly better:

other branch of the case analysis

Here you have a choice again -- but practically no matter which vertex you choose to focus your next case analysis on, it quickly turns out that both branches of that will be impossible too. (I will leave those last few details to you).

$\endgroup$
  • $\begingroup$ @ParclyTaxel: No, because I don't know. $\endgroup$ – Henning Makholm Oct 31 '18 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.