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 first-hand 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 sub-conjectures 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 4-color theorem; as it is a neat pair of facts that any planar trivalent graph with a Hamiltonian cycle has a 3-coloring of the edges, which is equivalent to having a 4-coloring 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 face-coloring 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 counter-example, 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 in-or-out 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, part-way 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 non-Hamiltonian 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 multiply-truncated, as shown by the fragment. In total it has 25 faces, 69 edges and 46 vertices. Euler be praised! And a rousing TA-DAH for Tutte! ------------------ That spelled the end of a "cheap" but satisfying method of proving the 4-color theorem. It was left till 30 years later for a proof to appear by the tedious and unsatisfying computer-aided 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 4-color; 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 non-Hamiltonian 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 non-Hamiltonian 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... SELF-COMPLEMENTARY ! |\ | / <---------------------------^^^^^^^^^^^^^^^^^^ | \ | / | \| / ======================================================== * * *---* Bill Taylor W.Taylor@math.canterbury.ac.nz ==========================================================================