Satz von Kruskal
# Satz von Kruskal

Der Satz von Kruskal ist ein Lehrsatz der Graphentheorie, eines der Teilgebiete der Mathematik. Er wurde von dem Mathematiker Joseph Bernard Kruskal im Jahre 1960 publiziert. Der Satz behandelt eine wichtige Eigenschaft der Klasse der endlichen Bäume.

## Formulierung des Satzes

Der Satz lässt sich angeben wie folgt:

    Die Klasse der endlichen Bäume ist durch die Quasiordnungsrelation der Bildung topologischer Minoren wohlquasigeordnet.
    Mit anderen Worten: Jede abzählbare Menge endlicher Bäume bildet zusammen mit der topologischen Minorenrelation eine wohlfundierte quasigeordnete Menge, in der jede Antikette endlich ist.

## Verwandte Sätze

Der Satz von Kruskal wurde in den 1960er Jahren von Crispin St. J. A. Nash-Williams auf unendliche Bäume verallgemeinert. Einen vereinfachten Beweis beider Sätze legte Daniela Kühn im Jahre 2001 vor. Der kruskalsche Satz ist eingebunden in den Problemkreis um das bedeutende Minorentheorem.

