Satz von Rédei (Graphentheorie)

In der Graphentheorie, einem der Teilgebiete der Mathematik, ist der Satz von Rédei ein Lehrsatz, der grundlegend für die Frage der Durchlaufbarkeit von Turniergraphen ist. Der Satz geht zurück auf eine Arbeit des ungarischen Mathematikers László Rédei aus dem Jahre 1934.^[1][2][3]

Formulierung des Satzes

Der rédeische Satz lässt sich zusammengefasst angeben wie folgt:

In einem endlichen Turnier mit mindestens zwei Knoten ist die Anzahl der darin vorkommenden hamiltonschen Bahnen stets eine ungerade Zahl.^[4]

Demnach gibt es in jedem endlichen Turnier mindestens eine Bahn, die jeden Knoten genau einmal enthält.

Anmerkungen zum Beweis

• Der zweite Teil des obigen Satzes von Rédei lässt sich leicht mittels vollständiger Induktion beweisen.^[1]
• Horst Sachs zufolge ist für den Satz insgesamt kein einfacher Beweis bekannt. Von dem ungarischen Mathematiker Tibor Szele wurde im Jahre 1943 ein (gemäß Sachs) sehr schöner kombinatorischer Beweis geliefert.^[3][5]

Literatur

• T. Szele: Kombinatorische Untersuchungen über gerichtete vollständige Graphen. In: Publicationes Mathematicae Debrecen. Band 13, 1966, S. 145–168 (math.klte.hu).  MR0207591
• Dénes König: Theorie der endlichen und unendlichen Graphen. Mit einer Abhandlung von L. Euler. Hrsg.: H. Sachs (= Teubner-Archiv zur Mathematik. Band 6). BSB B. G. Teubner Verlagsgesellschaft, Leipzig 1986, ISBN 3-211-95830-4. 
• Rudolf Halin: Graphentheorie (= Erträge der Forschung. Band 138). Band I. Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3 (MR0586234). 
• L. Rédei: Ein kombinatorischer Satz. In: Acta Scientiarum Mathematicarum; früher: Acta Litterarum ac Scientiarum (Sectio Scientiarum Mathematicarum), Szeged. Band 7, 1934, S. 39–43 (acta.fyx.hu). 
• Horst Sachs: Einführung in die Theorie der endlichen Graphen. Carl Hanser Verlag, München 1971, ISBN 3-446-11463-7.  MR0345857

Einzelnachweise und Fußnoten

1. ↑ ^{a b} Rudolf Halin: Graphentheorie I. 1980, S. 205 ff., 220–221
2. ↑ Dénes König: Theorie der endlichen und unendlichen Graphen. 1986, S. 29–31
3. ↑ ^{a b} Horst Sachs: Einführung in die Theorie der endlichen Graphen. 1971, S. 164–166
4. ↑ Horst Sachs (op. cit., S. 165) bezeichnet eine solche hamiltonsche Bahn auch als vollständige Bahn.
5. ↑ Publicationes Mathematicae Debrecen, Band 13, 1966, S. 145 ff.