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

Literatur

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.