Tutte's theorem (Hamilton circle problem)

In topological graph theory , one of the branches of mathematics , Tutte's theorem on the Hamilton circle problem is one of the theorems of the British-Canadian graph theorist William Thomas Tutte (1917–2002). Tutte published the theorem in 1956 and linked - following a result by Hassler Whitney from 1931 - the Hamilton circle problem with the question of flattening and multiple connections . The sentence is significant in relation to the four-color problem .

Formulation of the sentence

The sentence can be stated as follows:

If a finite, simple graph is flattenable and -fold connected , then it contains a Hamiltonian circle . ${\displaystyle G}$ ${\displaystyle 4}$ ${\displaystyle G}$

The sentence can also be formulated as follows:

In every finite, simple graph that is flattenable and does not contain a minimal cut with three or fewer nodes , there is a Hamiltonian circle. ${\displaystyle G}$

Whitney's theorem

The sentence submitted by Hassler Whitney in 1931 makes the same statement as the Tuttesche sentence, but does so under an additional condition. This is because the route graph representing the graph should also satisfy the condition that each country on its topological map is a triangular area in the Euclidean plane .

Relation to the four-color problem

As Hansjoachim Walther / Heinz-Jürgen Voß and Øystein Ore explain, the four-color problem has been solved for the topological maps of the graphs under consideration . Because such a graph can always be embedded in the surface of the unit sphere in such a way that the nodes of the Hamiltonian circle all come to lie on the equator of the sphere's surface. On this basis, it can be demonstrated by complete induction that both the countries of the northern hemisphere of the associated topological map and their countries in the southern hemisphere always have a permissible coloring with two colors , which is why the entire topological map allows a permissible coloring with four colors .

literature

• Øystein Ore : The Four-Color Problem. (=  Pure and Applied Mathematics . Volume 27 ). Academic Press, New York / London 1967 ( MR0216979 ).
• WT Tutte: A theorem on planar graphs . In: Transactions of the American Mathematical Society . tape 82 , 1956, pp. 99-116 , doi : 10.2307 / 1992980 ( MR0081471 ).
• Hansjoachim Walther, Heinz-Jürgen Voss: About circles in graphs . VEB Deutscher Verlag der Wissenschaften, Berlin 1974.
• Hassler Whitney: A theorem on graphs . In: Annals of Mathematics (2) . tape 32 , 1931, pp. 378-390 , doi : 10.2307 / 1968197 ( MR1503003 ).

References and footnotes

1. ↑ ^{a b c} Hansjoachim Walther, Heinz-Jürgen Voss: About circles in graphs. 1974, p. 26
2. ↑ Øystein Ore: The Four-Color Problem. 1967, p. 74
3. ↑ Ore, op. Cit., Pp. 105-108
4. ↑ This means, for example, for the proof of the four-color theorem , that in the context of a contradiction proof, the assumed smallest counterexample can be assumed as a flat, non -interconnected line graph. ${\displaystyle 4}$