From: mathwft@math.canterbury.ac.nz (Bill Taylor)
Newsgroups: sci.math
Subject: TUTTE'S fragment. An adventure in graph theory.
Date: 6 Oct 1997 06:15:37 GMT
While I was in London a few months ago, I had the pleasure and privilege of
attending a talk by Bill Tutte, one of the grand old men of graph theory.
He told us (among other things) the firsthand account of his ultimately
successful struggle to resolve Tait's conjecture, open since 1886. The
talk was a marvel of clarity and excitement, as he retraced his steps
through a bundle of subconjectures and resolutions, until he realized
that they combined to make up a resolution of Tait. And not only that,
but that the resolution was a constructive one. That it gave an actual
graph, that proved Tait's conjecture false. An exciting moment in math!
It'd be too hard to do the whole talk in ascii, alas, but here's the result:
Tait's conjecture:(1886) Every polyhedron has a Hamiltonian cycle
================= (along the edges) through ALL the vertices.
NOTE: If it were true, it would prove the 4color theorem; as it is a neat
pair of facts that any planar trivalent graph with a Hamiltonian cycle has a
3coloring of the edges, which is equivalent to having a 4coloring of faces.
To see the first, just color the Hamiltonian cycle alternately yellow and
red, then all the other edges are diagonals of this polygon, & can be blue.
To see the second, code the edge colors as (0,1) (1,0) and (1,1); then color
any face (0,0), and color the rest by crossing over edges using vector
addition [mod 2]. This gives a facecoloring in (0,0) (0,1) (1,0) & (1,1).
e.g. /
(1,0) /
/ ==> (0,1) It is fun to prove the equivalence. (One way
(1,1) is really easy, the other not quite so easy.)
/
Tutte's Fragment: (1946) < you can see from the date, that Tutte
================ is no chicken(!); in his 80's, I think.
Nonetheless, he was still as (mentally & physically) spry and enthusiastic
as any youngster, and conveyed the excitement of his discovery very well.
He proved Tait was false, by constructing a counterexample, as mentioned.
The key to this is what is now known as "Tutte's fragment", the following:


/\
/ \
/\ /\
/ \/ \
/  \
/  \
/ /\ \
/\ / \ /\
/ \ / \ / \
/ \/ \/ \
/ \ / \
/________\____/ \
/  \
/_________________________\
/ \
/ \
If this fragment is part of a larger graph, then any Hamiltonian cycle
through the graph MUST go inorout of the TOP vertex, (and either one
of the lower ones). It cannot go in one lower vertex & out the other.
Though this took some discovering, it is simple (if boring) to verify:
just sketch 3 such graphs and check out all the possibilities; 3 is enough
if common sense is applied.
Amusingly, Tutte was wearing a tie with a map of the fragment on it, which
he used to refer to, partway through the talk, when drawing it up on the
board, (as if he didn't know it by heart!) Unfortunately, several of us
were disappointed to learn that they were not commercially available! :(
The fragment can then be used to construct the nonHamiltonian polyhedron,
by putting together 3 such fragments as follows...
____
/\ F/\
/ \/ \ ...the three fragments (F) all have
/  \ their "compulsory" vertex facing
/  \ inwards; then it is easy to see
/ / \ \ there can be no Hamiltonian cycle.
/____/ \_____\
\ F / \ F / (The other 6 lines are just single
\ / \ / edges, with 3 faces, and as usual
v_________\/ another big face hidden underneath.)
A nice polyhedron, a tetrahedron (seen from above) with the bottom three
corners similarly multiplytruncated, as shown by the fragment.
In total it has 25 faces, 69 edges and 46 vertices.
Euler be praised! And a rousing TADAH for Tutte!

That spelled the end of a "cheap" but satisfying method of proving the
4color theorem. It was left till 30 years later for a proof to appear
by the tedious and unsatisfying computeraided method of checking
through several thousand unavoidable reducible configurations.
It might be thought that, therefore, Tutte's polyhedron might be more
than usually difficult to 4color; but no, it is rather easy in fact.
(There are 6 essentially different colorings of the fragment alone!)
Interestingly, the polyhedron above, (all "compulsories" inwards), is
not the only possibility. It is also possible to have them pointing
tangentially in cyclic order  this also leaves a nonHamiltonian
polyhedron, slightly different from the first. It is also possible to
reflect any fragment from side to side; effectlessly. Any other orientation
of the 3 fragments leaves a Hamiltonian cycle, though. (If the fragments
are oriented randomly, there is probability 8/9 of getting a Hamiltonian.)

Well, there are a few bits and pieces in there, for folk to amuse themselves
by checking out; but now I also have a question of my own. Two, in fact.
Firstly; does anyone know if it is possible to reduce the number of faces
of a nonHamiltonian polyhedron below 25 ? No obvious variant seems to work.
Secondly: I have a dim memory of having seen a paper in which Tutte's
fragment was used for something else, but I have no idea what it was now.
Can anyone else help out??
Thanks and cheers...

* * ** N.Z. graph theory is... SELFCOMPLEMENTARY !
\  / <^^^^^^^^^^^^^^^^^^
 \  /
 \ / ========================================================
* * ** Bill Taylor W.Taylor@math.canterbury.ac.nz
==========================================================================