Satz von Rédei (Graphentheorie)
# 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.

## 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.
    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.
