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:Reinhard Diestel: Graphentheorie. 2000, S. 251 ff., 253–255Reinhard Diestel: Graph Theory. 2005, S. 316 ff., 317Egbert Harzheim: Ordered Sets. 2005, S. 231 ff., 245–246Klaus Wagner: Graphentheorie. 1970, S. 172 ff., 178Rudolf Halin: Graphentheorie I. 1980, S. 116 ff. 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.Diestel, op. cit., S. 354 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.
Literatur Originalarbeiten MR0111704
Monografien
Einzelnachweise und Fußnoten
Kruskal