In der Mathematik stellt die Vermutung von Tait fest, dass "Jeder 3-verbundene planare Kubikgraph einen Zyklus von Hamiltonian (entlang den Rändern) durch alle seine Scheitelpunkte hat". Es wurde dadurch vorgeschlagen und dadurch widerlegt, wer ein Gegenbeispiel mit 25 Gesichtern, 69 Rändern und 46 Scheitelpunkten gebaut hat. Mehrere kleinere Gegenbeispiele, mit 21 Gesichtern, 57 Rändern und 38 Scheitelpunkten, wurden später minimal dadurch bewiesen.

Die Bedingung, dass der Graph, 3-regelmäßig sein, wegen Polyeder wie das rhombische Dodekaeder notwendig ist, das einen zweiteiligen Graphen mit sechs Grad vier Scheitelpunkte auf einer Seite und acht Grad drei Scheitelpunkte auf der anderen Seite bildet; weil jeder Zyklus von Hamiltonian zwischen den zwei Seiten des bipartition würde abwechseln müssen, aber sie haben ungleiche Zahlen von Scheitelpunkten, ist das rhombische Dodekaeder nicht Hamiltonian.

Die Vermutung könnte bedeutend gewesen sein, weil, wenn wahr, sie den vier Farbenlehrsatz einbezogen hätte: Wie Tait beschrieben hat, ist das vierfarbige Problem zum Problem gleichwertig, 3 Rand colorings bridgeless planarer Kubikgraphen zu finden. In Hamiltonian planarer Kubikgraph ist solch ein Rand, der sich färbt, leicht zu finden: Verwenden Sie zwei Farben abwechselnd auf dem Zyklus und einer dritten Farbe für alle restlichen Ränder. Wechselweise kann ein 4-Färben-von den Gesichtern von Hamiltonian planarer Kubikgraph direkt, mit zwei Farben für die Gesichter innerhalb des Zyklus und noch zwei Farben für die Gesichter draußen gebaut werden.

Das Gegenbeispiel von Tutte

Das Bruchstück von Tutte

Der Schlüssel zu diesem Gegenbeispiel ist, was jetzt als das Bruchstück von Tutte, gezeigt nach rechts bekannt ist.

Wenn dieses Bruchstück ein Teil eines größeren Graphen ist, dann muss jeder Zyklus von Hamiltonian durch den Graphen hineingehen oder aus dem Spitzenscheitelpunkt (und jeder der niedrigeren). Es kann in einen niedrigeren Scheitelpunkt und den anderen nicht hineingehen.

Das Gegenbeispiel

Das Bruchstück kann dann verwendet werden, um den non-Hamiltonian Graphen von Tutte, durch das Stellen zu bauen

zusammen drei solche Bruchstücke, wie gezeigt, auf dem Bild. Die "obligatorischen" Ränder der Bruchstücke, die ein Teil jedes Pfads von Hamiltonian durch das Bruchstück sein müssen, werden am Hauptscheitelpunkt verbunden; weil jeder Zyklus nur zwei dieser drei Ränder verwenden kann, kann es keinen Zyklus von Hamiltonian geben.

Der resultierende Graph von Tutte ist 3-verbunden und planar, so durch Steinitz' Lehrsatz ist es der Graph eines Polyeders. Insgesamt hat es 25 Gesichter, 69 Ränder und 46 Scheitelpunkte.

Es kann geometrisch von einem Tetraeder begriffen werden (dessen Gesichter den vier großen Gesichtern in der Zeichnung entsprechen, von denen drei zwischen Paaren von Bruchstücken sind, und von denen der vierte das Äußere bildet) dadurch multiplizieren das Beschneiden von drei seiner Scheitelpunkte.

Kleinere Gegenbeispiele

Als Show gibt es genau sechs non-Hamiltonian 38-Scheitelpunkte-Polyeder, die nichttriviale Drei-Ränder-Kürzungen haben. Sie werden gebildet, indem sie zwei der Scheitelpunkte eines fünfeckigen Prismas durch dasselbe im Beispiel von Tutte verwendete Bruchstück ersetzen.

Siehe auch

• Der Lehrsatz von Grinberg, eine notwendige Bedingung auf der Existenz eines Zyklus von Hamiltonian, der verwendet werden kann, um zu zeigen, dass ein Graph ein Gegenbeispiel zur Vermutung von Tait bildet
• Die Vermutung von Barnette, eine noch offene Verbesserung der Vermutung von Tait, die feststellt, dass jeder zweiteilige polyedrische Kubikgraph Hamiltonian ist.

Referenzen

• . Nachgedruckt in Wissenschaftlichen Zeitungen, Vol. II, Seiten 85-98.

Teilweise gestützt auf der Sci.math-Versetzung durch Bill Taylor, der durch die Erlaubnis verwendet ist.

Links