Tutte Fragment

Author

Eric W. Weisstein
June 8, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/TutteFragment.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/TutteFragment.html.

©2023 Wolfram Research, Inc. except for portions noted otherwise

Sources

Taylor 1997

https://web.archive.org/web/20110910090533/http://www.math.niu.edu/~rusin/known-math/97/tutte

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
==========================================================================

Wikipedia

https://en.wikipedia.org/wiki/Walther_graph

Construction

v={{57.25390625`,209.10546875`},{90.609375`,249.3515625`},{138.5859375`,270.2421875`},{138.23046875`,226.68359375`},{196.93359375`,236.89453125`},{234.50390625`,166.74609375`},{173.55078125`,152.6953125`},{140.48046875`,181.66796875`},{96.671875`,180.046875`},{88.33203125`,144.51953125`},{37.52734375`,152.0390625`},{134.32421875`,110.671875`},{235.66015625`,74.98046875`},{126.19921875`,64.9296875`},{38.4921875`,93.00390625`}}/250;

Graph[Range@Length@v,UndirectedEdge@@@{e[15,14,13,6,5,3,2,1,11,15],e[14,12,7,8,9,10,12],{10,11},{1,9},e[2,4,5],{4,8},{7,6}},VertexCoordinates->v]

GraphPlot@%

EuclideanDistance@@v[[{2,6}]]

RegionIntersection[InfiniteLine@v[[{2,12}]],Line@v[[{6,8}]]]

v={{-1,0},{0,Sqrt[3]},{1,0}};
v=Join[v,Subdivide[{-1,0},{0,Sqrt[3]},4][[2;;-2]]];
v=Join[v,{-#,#2}&@@@v[[{4,6}]],{{-(1/4),((Sqrt[3])/2)},{-(3/8),((Sqrt[3])/4)},{0,((Sqrt[3])/4)},{(1/4),((Sqrt[3])/2)},{(3/8),((Sqrt[3])/4)},{(1/8),((3 (Sqrt[3]))/4)},v[[2]]+{0,1/2},{0,0}}];
v=(#-v[[15]])&/@v;

tuttefragment0=Graph[Range@Length@v,Sort[Sort/@(UndirectedEdge@@@{e[1,16,3,7,8,2,6,5,4,1],e[4,10,11,13,7],e[5,9,12],e[6,14,8],{11,16},{9,10},e[14,12,13]})],VertexCoordinates->v,VertexLabels->Automatic]

VertexCount[%]

tuttefragment1=VertexDelete[tuttefragment0,15]

tuttefragment=IndexGraph@Annotate[tuttefragment1,VertexCoordinates->((1/((2+(1/(Sqrt[3]))))){#(((Sqrt[3])+(1/2))/(Sqrt[3])),#2}&@@@GraphEmbedding[tuttefragment1])]

hp=Cases[MyFindHamiltonianPath[GraphData["TutteFragment"],All],{1|2|3,__,1|2|3}]

GraphicsGrid[Partition[HighlightGraph[GraphData["TutteFragment"],UndirectedEdge@@@Partition[#,2,1],GraphHighlightStyle->"Thick"]&/@hp,3],ImageSize->700]

Annotate[tuttefragment,VertexLabels->None]//StyleGraphs

Embeddings

<<MathWorld`Graphs`

Names

GraphData["TutteFragment","StandardName"]

GraphData["TutteFragment","StandardNames"]

Primary

GraphData["TutteFragment"]//StyleGraphs[#,ImageSize->Small]&

All

GraphData["TutteFragment","Graph","All"]//StyleGraphs

Inexact

Select[GraphData["TutteFragment","Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData["TutteFragment","EdgeList"]]

Default embedding

GraphPlot@RotateGraph[Graph@GraphData["TutteFragment","Edges"],Pi/2]

v=Join[CirclePoints[9],CirclePoints[1/2,5]];
AppendTo[v,Mean[v[[{4,6}]]]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[{1,9},1,10,11,12,13,14,10],{8,14},{7,13},{11,3},{12,15},e[6,15,4]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

v={{0,0},{2,0},{4,0},{0,1},{1,1},{2,1},{3,1},{4,1},{1,2},{3,2},{0,3},{1,3},{3,3},{4,3},{4+3Sqrt[3]/2,3/2}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,15,14,13,12,11,4,1],e[4,5,6,7,8],{9,10},e[5,9,12],{2,6},e[7,10,13],e[3,8,14]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

g=VertexDelete[LabelGraph@GraphData["TutteGraph"],Complement[Range[46],{9,10,23,24,25,21,17,18,19,16,15,8,22,14,11}]]

v=Round[GraphEmbedding[%205]5/900]/5

g=Annotate[g,VertexCoordinates->v]

g=;

RecognizeGraph@g

Degenerate

GraphData["TutteFragment","Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData["TutteFragment","Graph","Degenerate"]

Bilateral

GraphData["TutteFragment","Graph","Bilateral"]//StyleGraphs

Circular

GraphData["TutteFragment","Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData["TutteFragment"],All][[All,All,1]]]

CircularEmbeddingFromHamiltonianCycle[GraphData["TutteFragment"],#]&/@hc

g=;

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData["TutteFragment"],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData["TutteFragment","Planar"]

GraphData["TutteFragment","Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData["TutteFragment",{"RCN","CN"}]

GraphData["TutteFragment","Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData["TutteFragment"],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData["TutteFragment"],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData["TutteFragment"],"CrossingNumber"->cn])//PolyhedralGraphQ

GraphData["TutteFragment","Polyhedral"]

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData["TutteFragment"],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData["TutteFragment","V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData["TutteFragment"],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["TutteFragment","Circulant"]

GraphData["TutteFragment","Graph","Circulant"]//StyleGraphs

Line graph

GraphData["TutteFragment","Line"]

LineGraphQ[GraphData["TutteFragment"]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== "TutteFragment"&]

RootGraph[GraphData["TutteFragment"]]

Halin

GraphData["TutteFragment","Halin"]

GraphData["TutteFragment","Graph","Halin"]//StyleGraphs

Rigid

GraphData["TutteFragment","Rigid"]

GraphData["TutteFragment","Graph","Rigid"]//StyleGraphs

Flexible

GraphData["TutteFragment","Flexible"]

GraphData["TutteFragment","Graph","Flexible"]//StyleGraphs

LCF

GraphData["TutteFragment","LCF"]

GraphData["TutteFragment","HamiltonianCycleCount"]

GraphData["TutteFragment","LCFSignature"]

GraphData["TutteFragment","LCFNotations"]

GraphData["TutteFragment","Graph","LCF"]//StyleGraphs

UnitDistance

GraphData["TutteFragment","UnitDistance"]

UnitDistanceGraphQ[GraphData["TutteFragment"],Debug->True]//Timing

GraphData["TutteFragment","Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["TutteFragment","VertexList"],GraphData["TutteFragment","EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData["TutteFragment","Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData["TutteFragment"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData["TutteFragment"],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistanceGraphEmbeddingQ/@{,}

UnitDistance by FindSubgraphUnitDistanceEmbedding

{ "TutteFragment",l=FindSubgraphUnitDistanceEmbedding[GraphData["TutteFragment"],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

gs={,};

Matchstick

GraphData["TutteFragment","Matchstick"]

GraphData["TutteFragment","Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData["TutteFragment","Edges"]]

3D All

GraphData["TutteFragment","Graph",{"3D","All"}]

3D UnitDistance

GraphData["TutteFragment","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["TutteFragment","Polyhedral"]

Construction of Tutte graph

subg=VertexDelete[tuttefragment0,{17,18}]

v=GraphEmbedding[subg];

n=Length[v]

vs=Flatten[Table[RotationMatrix[Pi+2Pi i/3].#&/@v,{i,0,2}],1];

g=EdgeAdd[ContractCoincidentVertices@Graph[Range[3Length[v]],UndirectedEdge@@@Flatten[Table[EdgeList[subg]/.k_Integer:>k+i n,{i,0,2}],1],VertexCoordinates->vs,VertexLabels->Automatic],UndirectedEdge@@@{{35,1},{17,3},{19,33}}]

RecognizeGraph@g

VertexCount[g]

GraphData

GraphClassString

GraphDataClassString["TutteFragment"]

GraphDataString

<<MathWorld`Graphs`

file=OpenWrite["~/tutte.m"]

WriteString[file,GraphDataString[tuttefragment,
"StandardName"->"TutteFragment",
"Name"->"Tutte fragment",
"Information"->"TutteFragment",
"Skip"->{}
]]

Close[file]