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.Rudolf Halin: Graphentheorie I. 1980, S. 205 ff., 220–221Dénes König: Theorie der endlichen und unendlichen Graphen. 1986, S. 29–31Horst Sachs: Einführung in die Theorie der endlichen Graphen. 1971, S. 164–166
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.Horst Sachs (op. cit., S. 165) bezeichnet eine solche hamiltonsche Bahn auch als vollständige Bahn. 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. 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.Publicationes Mathematicae Debrecen, Band 13, 1966, S. 145 ff.
Literatur
MR0345857 MR0207591
Einzelnachweise und Fußnoten
Redei