Satz von Tutte (Hamiltonkreisproblem)

In der Topologischen Graphentheorie, einem der Teilgebiete der Mathematik, ist der Satz von Tutte zum Hamiltonkreisproblem einer der Lehrsätze des britisch-kanadischen Graphentheoretikers William Thomas Tutte (1917–2002). Tutte publizierte den Satz im Jahre 1956 und verknüpft dabei – an ein Resultat von Hassler Whitney aus dem Jahre 1931 anschließend – das Hamiltonkreisproblem mit der Frage der Plättbarkeit und des mehrfachen Zusammenhangs. Der Satz ist bedeutsam in Bezug auf das Vier-Farben-Problem.

Formulierung des Satzes

Der Satz lässt sich angeben wie folgt:

Ist ein endlicher schlichter Graph $G$ plättbar und $4$-fach zusammenhängend, so enthält $G$ einen hamiltonschen Kreis.

Der Satz lässt sich auch so formulieren:

In jedem endlichen schlichten Graphen $G$, der plättbar ist und keinen minimalen Schnitt mit drei oder weniger Knoten enthält, gibt es einen hamiltonschen Kreis.

Der whitneysche Satz

Der von Hassler Whitney 1931 vorgelegte Satz macht die gleiche Aussage wie der tuttesche Satz, tut dies allerdings unter einer zusätzlichen Voraussetzung. Es soll nämlich hier der den Graphen darstellenden Streckengraph zusätzlich der Bedingung genügen, dass jedes Land seiner topologischen Landkarte eine Dreiecksfläche in der euklidischen Ebene ist.

Bezug zum Vier-Farben-Problem

Wie Hansjoachim Walther/Heinz-Jürgen Voß und Øystein Ore ausführen, ist für die topologischen Landkarten der betrachteten Graphen das Vier-Farben-Problem gelöst. Denn ein solcher Graph lässt sich stets derart in die Oberfläche der Einheitskugel einbetten, dass die Knoten des hamiltonschen Kreises sämtlich auf dem Äquators der Kugeloberfläche zu liegen kommen. Davon ausgehend lässt sich durch vollständige Induktion nachweisen, dass sowohl die Länder der Nordhalbkugel der zugehörigen topologischen Landkarte als auch ihre Länder auf der Südhalbkugel stets eine zulässige Färbung mit zwei Farben besitzen, weswegen die gesamte topologische Landkarte eine zulässige Färbung mit vier Farben gestattet.

Literatur

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