Endliche und unendliche Graphen erklärt

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Die Definition hat nie „endlich“ gesagt

Kehren Sie zur Definition im Leitfaden zu Knoten und Kanten zurück und lesen Sie, was sie tatsächlich sagt:

G = (V, E)      with   E ⊆ [V]²

Eine Knotenmenge und eine Menge 2-elementiger Teilmengen davon. Nichts davon erwähnt die Größe. V kann aus den vier Landmassen Königsbergs, den ganzen Zahlen, den reellen Zahlen oder der Menge aller endlichen Binärstrings bestehen, und die Definition zuckt nicht mit der Wimper. Ein unendlicher Graph ist einfach ein Graph mit unendlicher Knotenmenge, und das ganze Thema dieses Artikels ist, was dann unbemerkt nicht mehr funktioniert.

Das ist keine moderne Verfeinerung. Das erste Buch über Graphentheorie überhaupt ist Dénes Königs Theorie der endlichen und unendlichen Graphen von 1936, dessen Titel bereits beide Fälle nennt. Unendliche Graphen gehören seit dem ersten Lehrbuch zum Fach, und Diestels Graph Theory widmet ihnen noch immer ein ganzes Kapitel.

Der entscheidende Schritt ist zu bemerken, dass „endlich“ eine Annahme ist, die Sie benutzt haben, ohne sie zu sehen. Die meisten Lehrbuchaussagen haben die Form „Sei G ein endlicher Graph“, und die meisten Standardbeweistechniken brauchen es stillschweigend:

• Induktion über die Knotenzahl braucht eine Knotenzahl, über die man induzieren kann.
• Extremalargumente („nimm den Knoten maximalen Grades“, „nimm den längsten Weg“) brauchen, dass das Maximum oder der längste Weg existiert.
• Zählargumente brauchen endliche Anzahlen statt Kardinalzahlen.
• Die Terminierung eines Algorithmus braucht, dass der Suche der Graph ausgeht.

Nimmt man die Endlichkeit weg, muss jedes davon durch etwas anderes ersetzt werden. Was sie ersetzt, ist fast immer Kompaktheit: die Idee, dass sich eine Aussage über ein unendliches Objekt manchmal aus Aussagen über alle seine endlichen Teile zusammensetzen lässt. Die Abschnitte 5 und 6 behandeln die zwei klassischen Sätze, die genau das tun.

2. Wie groß: abzählbar, überabzählbar, lokal endlich

„Unendlich“ ist keine einzelne Größe, und drei getrennte Messgrößen sind wichtig. Sie zu verwechseln ist die erste Quelle der Verwirrung.

Ein Graph ist lokal endlich , wenn jeder Knoten endlichen Grad hat. Das ist eine wirklich von der Abzählbarkeit unabhängige Bedingung, und die beiden treten in allen vier Kombinationen auf:

• Der Doppelstrahl, ein in beide Richtungen unendlicher Weg, ist abzählbar und lokal endlich: Jeder Grad ist 2.
• Das unendliche quadratische Gitter auf ℤ² ist abzählbar und lokal endlich: Jeder Grad ist 4. Auf diesem Graphen leben Tabellenkalkulationen, Zellularautomaten und gekachelte Spielwelten tatsächlich.
• Der unendliche Stern, ein Zentrum, das mit abzählbar vielen Blättern verbunden ist, ist abzählbar, aber nicht lokal endlich: Das Zentrum hat unendlichen Grad.
• Der vollständige Graph auf einer überabzählbaren Knotenmenge ist überabzählbar und nicht lokal endlich.
• Eine überabzählbare Familie disjunkter Doppelstrahlen ist überabzählbar und dennoch lokal endlich: Es gibt überabzählbar viele Knoten, und jeder davon hat trotzdem den Grad 2. Das ist die vierte Kombination, und sie zeigt, dass keine der beiden Bedingungen etwas über die andere aussagt.

Eine Folgerung verdient eine eigene Erwähnung, weil sie viele stolpern lässt: Ein lokal endlicher Graph kann trotzdem unendlich sein, und ein unendlicher Graph kann lauter kleine Grade haben. Lokale Endlichkeit beschränkt jeden Knoten einzeln; über die Größe des Graphen sagt sie nichts.

3. Was die Endlichkeit stillschweigend leistete

Hier ist die ehrliche Bestandsaufnahme. Das sind Standardresultate und Standardtechniken, und jede scheitert auf unendlichen Graphen aus einem bestimmten Grund.

Zwei Zeilen verdienen sofort einen Kommentar, weil sie am meisten überraschen.

„Ein Knoten hat maximalen Grad“ scheitert, und zwar aus dem banalsten Grund der Analysis: Eine unendliche Menge natürlicher Zahlen muss kein größtes Element enthalten. Bauen Sie einen Graphen, dessen Knoten die Grade 1, 2, 3 und so weiter ohne Schranke haben, und die Größe Δ(G) ist schlicht nicht definiert. Jedes Extremalargument, das mit „Sei v ein Knoten maximalen Grades“ beginnt, hat daher stillschweigend Endlichkeit vorausgesetzt, oder zumindest eine Schranke.

Der unendliche Stern bricht Königs Lemma, und deshalb steht die lokale Endlichkeit in seiner Formulierung. Der Stern ist unendlich und zusammenhängend, doch sein längster Weg hat die Länge 2: Blatt, Zentrum, Blatt. Er enthält nirgends einen Strahl. Ein einziger Knoten unendlichen Grades genügt, um die Folgerung zu zerstören, was zeigt, dass die Voraussetzung echte Arbeit leistet und keine technische Hygiene ist.

4. Ein Gegenbeispiel in einer Zeile zur Folgerung aus dem Handschlaglemma

Das Handschlaglemma ist der älteste Satz des Fachs, und an seine Folgerung erinnert sich jeder: Die Anzahl der Knoten mit ungeradem Grad ist gerade. Auf unendlichen Graphen ist sie falsch, und das Gegenbeispiel ist mit einer Zeile gezeichnet.

Nehmen Sie den Strahl: Knoten v0, v1, v2, … mit einer Kante zwischen aufeinanderfolgenden Knoten.

v0 ── v1 ── v2 ── v3 ── v4 ── ⋯

deg(v0) = 1        ungerade
deg(vi) = 2        gerade, für jedes i ≥ 1

Knoten mit ungeradem Grad: genau einer.  Die endliche Folgerung sagt, ihre Anzahl müsse gerade sein.

Es lohnt sich, genau zu sagen, was überlebt, denn die Antwort ist interessanter als ein pauschales „es scheitert“.

Die Gleichung ∑ deg(v) = 2|E| wird nicht falsch, sondern inhaltsleer. Beide Seiten sind Kardinalzahlen, und für eine unendliche Kardinalzahl κ gilt 2κ = κ, also gilt die Identität trivialerweise und sagt nichts aus. Was tatsächlich bricht, ist das darauf aufgebaute Paritätsargument . Dieses Argument teilt eine endliche Summe in ungerade und gerade Teile und folgert, dass der ungerade Teil eine gerade Anzahl von Summanden hat, und es ist die Endlichkeit der Summe, nicht die Gleichung, die diesen Schritt erlaubt.

Die Lehre verallgemeinert sich: Wenn ein endlicher Satz auf unendlichen Graphen scheitert, bricht meist nicht die Aussage, sondern die Beweistechnik, und diese Technik ist meist das Zählen.

5. Königs Unendlichkeitslemma: die erste Brücke

Wenn die meisten Beweise auf Endlichkeit beruhen, ist die interessante Frage, was sie ersetzen kann. Die erste und nützlichste Antwort ist ein Lemma, das König 1927 veröffentlichte, neun Jahre vor seinem Lehrbuch.

Königs Unendlichkeitslemma. Jeder unendliche, zusammenhängende, lokal endliche Graph enthält einen Strahl, also einen unendlichen Weg v0, v1, v2, … ohne wiederholten Knoten.

Der Beweis ist ein unendlich oft ausgeführtes Schubfachargument, und es lohnt sich, ihn zu sehen, weil diese Gestalt in der ganzen unendlichen Kombinatorik wiederkehrt.

Beginnen Sie bei einem beliebigen Knoten v0. Der Graph ist unendlich und zusammenhängend, also sind von dort unendlich viele Knoten erreichbar. Der Graph ist lokal endlich, also hat v0 nur endlich viele Nachbarn. Das Löschen von v0 verteilt diese unendlich vielen übrigen Knoten auf endlich viele Teile, also ist nach dem Schubfachprinzip mindestens ein Teil unendlich. Gehen Sie hinein, und Sie sind in genau der Situation, in der Sie begonnen haben. Endloses Wiederholen liefert v0, v1, v2, …, und weil jeder Schritt in einen noch nicht besuchten Bereich führt, wiederholt sich kein Knoten.

Beide Voraussetzungen leisten Arbeit, und das Weglassen einer davon zerstört die Folgerung:

• Ohne lokale Endlichkeit ist der unendliche Stern ein Gegenbeispiel: unendlich, zusammenhängend, und sein längster Weg hat 3 Knoten.
• Ohne Unendlichkeit gibt es nichts zu beweisen.

Das Lemma reicht weit über die Graphentheorie hinaus. In seiner Baumform, „ein unendlicher, endlich verzweigter Baum hat einen unendlichen Ast“, ist es der kombinatorische Kern von Kompaktheitsargumenten in der Logik, und es erlaubt den Schluss, dass eine Berechnung mit unendlich vielen endlichen Zuständen einen unendlichen Lauf haben muss. Es ist dieselbe Idee, die dem Kompaktheitssatz der Aussagenlogik zugrunde liegt, und von dort kommt der nächste Abschnitt.

6. De Bruijn und Erdős: Färbbarkeit überträgt sich

Die zweite große Brücke nimmt eine Eigenschaft, die sich auf endlichen Teilen prüfen lässt, und hebt sie auf den ganzen unendlichen Graphen.

Satz von De Bruijn und Erdős (1951). Für ein endliches k ist ein unendlicher Graph genau dann k-färbbar, wenn jeder seiner endlichen Teilgraphen k-färbbar ist.

Die Richtung „nur dann“ ist trivial: Eine Färbung des ganzen Graphen schränkt sich auf jeden Teilgraphen ein. Der Gehalt liegt in der anderen Richtung, und sie ist wirklich überraschend. Sie besagt, dass Färbbarkeit, also eine globale Bedingung über unendlich viele Knoten gleichzeitig, vollständig durch das bestimmt ist, was auf endlichen Ausschnitten geschieht. „Im Unendlichen“ kann nichts Neues schiefgehen.

Zwei Einschränkungen, die wichtig sind und die populäre Darstellungen meist übergehen:

• Die Anzahl der Farben muss endlich sein. Der Satz handelt von einem festen endlichen k. Er besagt nicht, dass ein Graph, dessen endliche Teilgraphen alle mit endlich vielen Farben färbbar sind, selbst mit endlich vielen Farben färbbar ist.
• Er braucht ein Auswahlprinzip. Die Standardbeweise laufen über den Satz von Tychonoff für kompakte Hausdorff-Räume, das Lemma von Zorn oder das Ultrafilterlemma. In der Zermelo-Fraenkel-Mengenlehre ganz ohne Auswahl ist der Satz nicht beweisbar. De Bruijn und Erdős arbeiteten mit dem Auswahlaxiom, wie fast alle.

Die praktische Lesart für alle, die unbeschränkte Systeme modellieren: Wenn sich Ihre Bedingung als Färbung mit einer festen endlichen Palette ausdrücken lässt, können Sie sie auf endlichen Fragmenten prüfen und auf das Ganze schließen. Genau diese Erlaubnis gibt ein Kompaktheitsargument, und deshalb kann endliches Model Checking manchmal etwas über unbeschränkte Läufe aussagen.

7. Strahlen, Doppelstrahlen und Enden

Die endliche Graphentheorie hat kein Vokabular für „wie der Graph weit draußen aussieht“, weil ein endlicher Graph kein „weit draußen“ hat. Die unendliche Graphentheorie braucht eines, und die Standardkonstruktion stammt von Halin.

• Ein Strahl ist ein einseitig unendlicher Weg v0, v1, v2, …. Königs Lemma besagt, dass jeder unendliche, zusammenhängende, lokal endliche Graph einen enthält.
• Ein Doppelstrahl ist ein beidseitig unendlicher Weg, indiziert durch ganz ℤ. Er ist ein unendlicher Baum ganz ohne Blätter, und genau das kann kein endlicher Baum sein.
• Ein Ende ist eine Äquivalenzklasse von Strahlen, wobei zwei Strahlen als äquivalent gelten, wenn keine endliche Knotenmenge sie trennt. Enden sind die formale Antwort auf die Frage, in wie viele verschiedene Richtungen dieser Graph ins Unendliche läuft.

Der Begriff ist über Beispiele leichter zu erfassen als über die Definition:

Der Gittereintrag ist der lehrreiche. Intuitiv läuft eine Ebene in jede Richtung davon, man würde also viele Enden erwarten, aber die Definition fragt, ob sich Strahlen durch das Entfernen endlich vieler Knoten trennen lassen, und in einem Gitter geht das nicht: Geht man weit genug hinaus, kann man jedes endliche Loch immer umlaufen. Ein Ende ist die richtige Antwort, und es ist die Definition, nicht das Bild, die das entscheidet.

8. Spannbäume und das Auswahlaxiom

Jeder endliche zusammenhängende Graph hat einen Spannbaum, und der Beweis ist ein zweizeiliges Greedy-Argument: Löschen Sie so lange eine Kante, die auf einem Kreis liegt, bis keine mehr übrig ist. Das terminiert, weil es endlich viele Kanten gibt.

Die unendliche Aussage ist immer noch wahr, aber aus einem anderen und viel tieferen Grund:

Jeder zusammenhängende Graph hat einen Spannbaum. Für unendliche Graphen erfordert das das Auswahlaxiom, und die Aussage ist sogar zu ihm äquivalent.

Der übliche Beweis wendet das Lemma von Zorn auf die Familie der kreisfreien Teilgraphen an, geordnet durch Inklusion, und das ist ein verkapptes Auswahlprinzip. Dass die Implikation in beide Richtungen gilt, dass also „jeder zusammenhängende Graph hat einen Spannbaum“ nicht bloß eine Folge des Auswahlaxioms ist, sondern ebenso stark wie dieses, ist ein wirklich bemerkenswertes Resultat: Eine harmlos aussehende Aussage über Graphen erweist sich als eine der vielen äquivalenten Formen eines mengentheoretischen Axioms.

Die praktische Bedeutung ist gering, die begriffliche groß. Kein Algorithmus, den Sie schreiben, ist davon betroffen, weil die Graphen, die ein Programm berührt, endlich oder zumindest berechenbar gegeben sind. Aber es markiert genau die Stelle, an der unendliche Graphentheorie aufhört, Kombinatorik zu sein, und beginnt, Mengenlehre zu sein, und es erklärt, warum Lehrbücher über unendliche Graphen sorgfältig angeben, welche Auswahlprinzipien sie voraussetzen.

Dasselbe Muster kehrt anderswo wieder. Mehrere Aussagen, die für endliche Graphen Routine sind, hängen in ihrer unendlichen Fassung vom Auswahlaxiom ab oder sind von den Grundaxiomen unabhängig, und deshalb trägt auch De Bruijn-Erdős eine Auswahlvoraussetzung.

9. Der Rado-Graph: ein Graph, sie alle zu beherrschen

Unendliche Graphen sind nicht bloß endliche Graphen mit mehr von allem. Manche verhalten sich auf eine Weise, die überhaupt kein endliches Gegenstück hat, und das klarste Beispiel ist der Rado-Graph.

Man sagt, ein abzählbarer Graph habe die Erweiterungseigenschaft , wenn es für jedes Paar disjunkter endlicher Knotenmengen U und W einen Knoten gibt, der mit jedem Knoten in U und mit keinem in W verbunden ist. Dann gilt:

Eindeutigkeit. Je zwei abzählbare Graphen mit der Erweiterungseigenschaft sind isomorph. Es gibt bis auf Isomorphie genau einen solchen Graphen: den Rado-Graphen, auch Zufallsgraph R genannt.

Und warum er Zufallsgraph heißt, ist die zweite Hälfte der Geschichte. Erdős und Rényi zeigten: Baut man einen abzählbar unendlichen Graphen, indem man über jede mögliche Kante unabhängig mit Wahrscheinlichkeit 1/2 entscheidet, so hat das Ergebnis mit Wahrscheinlichkeit 1 die Erweiterungseigenschaft. Also:

Werfen Sie für jedes Knotenpaar einer abzählbar unendlichen Menge eine faire Münze.
Mit Wahrscheinlichkeit 1 ist der entstehende Graph der Rado-Graph.
Tun Sie es noch einmal, anders. Sie erhalten wieder den Rado-Graphen, bis auf Isomorphie.

Es gibt im Wesentlichen einen abzählbar unendlichen Zufallsgraphen. Nichts auch nur entfernt Ähnliches geschieht bei endlichen Graphen, wo Zufallsgraphen mit n Knoten äußerst vielfältig sind und sich alle interessanten Fragen darum drehen, welche Eigenschaften mit hoher Wahrscheinlichkeit gelten. Der Rado-Graph enthält außerdem jeden endlichen und jeden abzählbaren Graphen als induzierten Teilgraphen, was ihn universell für abzählbare Graphen macht.

Für die Praxis zählt nicht die Konstruktion selbst, sondern die Warnung, die sie enthält: An endlichen Graphen geschulte Intuitionen sind im Unendlichen nicht nur quantitativ, sondern qualitativ falsch. „Zufällig“ bedeutet nicht mehr „vielfältig“, sondern „kanonisch“.

10. Wann unendlich einfacher ist

Man könnte vernünftigerweise annehmen, unendliche Graphen seien durchweg schwieriger. Manchmal ist das Gegenteil wahr, und die Ramsey-Theorie ist das Standardbeispiel.

Ramsey bewies beide in seiner Arbeit von 1930. Die unendliche Version ist gerade deshalb einfacher, weil sie keine Schranke verlangt: Man muss nie sagen, wie weit draußen die einfarbige Struktur auftritt, nur dass sie auftritt. Die endliche Version lässt sich aus der unendlichen gewinnen, durch ein Kompaktheitsargument aus derselben Familie wie Königs Lemma, aber die gelieferten Schranken sind miserabel, und deshalb ist die endliche Ramsey-Theorie ein eigenes und viel schwierigeres Gebiet.

Die allgemeine Lehre: Unendliche Aussagen sind oft sauberer, weil sie nicht quantitativ sind. Wenn ein endlicher Satz wegen seiner Schranken schwer ist, kann sein unendliches Gegenstück viel einfacher sein und trotzdem etwas Nützliches sagen.

11. Unendliche Graphen in der Informatik

Unendliche Graphen sind keine rein mathematische Liebhaberei. Sie tauchen in der Informatik ständig auf, meist implizit und immer in derselben verkleideten Form: als Graph, den man nie aufbaut.

• Zustandsräume. Der Konfigurationsgraph einer Turingmaschine, eines Programms mit unbeschränkten ganzen Zahlen oder eines Protokolls mit unbeschränkten Warteschlangen ist unendlich. Das Model Checking eines solchen Systems ist genau die Untersuchung eines unendlichen Graphen, der durch eine endliche Beschreibung gegeben ist.
• Gitter. Wegsuche auf einer unbeschränkten Kachelkarte, Zellularautomaten und Bildgitter leben alle auf ℤ², einem unendlichen, lokal endlichen Graphen.
• Spielbäume. Der vollständige Baum eines Spiels ohne Zuglimit ist unendlich; Suchalgorithmen erkunden ein endliches Anfangsstück davon.
• Cayley-Graphen. Eine unendliche Gruppe mit gewähltem Erzeugendensystem liefert einen unendlichen knotentransitiven Graphen, und die geometrische Gruppentheorie untersucht Gruppen genau über diese Graphen und ihre Enden.
• Rekursiv definierte Strukturen. Der Graph aller endlichen Strings unter „ein Zeichen anhängen“ ist ein unendlicher Baum, und auf dieses Objekt wird Königs Lemma in der Berechenbarkeitstheorie meist angewandt.

Die technische Folge ist eine einzige scharfe Unterscheidung:

Auf einem unendlichen, lokal endlichen Graphen wird Suche semi-entscheidbar. Eine Breitensuche von s aus findet einen Weg zu t , falls einer existiert, und läuft endlos, falls keiner existiert. Die lokale Endlichkeit sorgt dafür, dass jede Ebene endlich ist, sodass die Suche jede Distanz in endlicher Zeit erreicht. Sie kann Erreichbarkeit bestätigen, aber nie widerlegen.

Diese Asymmetrie ist der Grund, warum BFS statt DFS auf einem unendlichen Graphen die richtige Wahl ist: BFS erkundet nach Distanz geordnet und erreicht jeden erreichbaren Knoten in endlicher Zeit, während DFS einen einzigen unendlichen Ast hinabsteigen und nie zurückkehren kann. Aus demselben Grund gibt es die iterative Tiefensuche. Für Terminierung braucht man etwas Zusätzliches, etwa lokale Endlichkeit plus eine Schranke, ein monoton fallendes Maß oder eine endliche Abstraktion des Zustandsraums.

12. Häufige Fehler

• Annehmen, ein Maximum oder Minimum existiere. „Nimm den Knoten maximalen Grades“ und „nimm den längsten Weg“ setzen beide Endlichkeit oder eine ausdrückliche Schranke voraus. Auf einem unendlichen Graphen bezeichnen sie womöglich gar nichts.
• Die Folgerung über ungerade Grade verwenden. Der Strahl hat genau einen Knoten mit ungeradem Grad, wie Abschnitt 4 zeigt.
• Über die Knotenzahl induzieren. Eine solche Zahl gibt es nicht. Transfinite Induktion steht zur Verfügung, braucht aber eine Wohlordnung, was ein weiterer Rückgriff auf das Auswahlaxiom ist.
• Die lokale Endlichkeit in Königs Lemma vergessen. Der unendliche Stern ist unendlich, zusammenhängend und enthält keinen Strahl. Die Voraussetzung ist keine Dekoration.
• Terminierung erwarten. Suche auf einem unendlichen Graphen ist semi-entscheidbar, eine Antwort „kein Weg“ kommt also nie an. Beschränken Sie die Suche ausdrücklich oder arbeiten Sie mit einer endlichen Abstraktion.
• DFS auf einem unendlichen Graphen ausführen. Ein einziger unendlicher Ast verschluckt sie. Verwenden Sie BFS oder iterative Tiefensuche.
• Endliche Zählresultate anwenden. Alles, was durch Zählen von Knoten, Kanten oder Inzidenzen bewiesen wurde, muss neu geprüft werden; alles, was durch Kompaktheit bewiesen wurde, überlebt meist.
• „Unendlich“ als eine einzige Sache behandeln. Abzählbar gegenüber überabzählbar und lokal endlich gegenüber nicht lokal endlich sind unabhängig, und fast jeder Satz hängt davon ab, welche Kombination vorliegt.

13. Glossar

15. Quellen

Die Definitionen, Sätze und Zuschreibungen oben stammen aus diesen Quellen, in chronologischer Reihenfolge.

1. König, D. (1927). "Über eine Schlussweise aus dem Endlichen ins Unendliche." Acta Litterarum ac Scientiarum Regiae Universitatis Hungaricae Francisco-Josephinae, Sectio Scientiarum Mathematicarum (Szeged) 3, 121 bis 130. Das Unendlichkeitslemma.
2. Ramsey, F. P. (1930). "On a Problem of Formal Logic." Proceedings of the London Mathematical Society s2-30, 264 bis 286. Enthält den endlichen und den unendlichen Satz von Ramsey.
3. König, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft. Das erste Buch über Graphentheorie, und sein Titel nennt bereits beide Fälle.
4. de Bruijn, N. G. and Erdős, P. (1951). "A Colour Problem for Infinite Graphs and a Problem in the Theory of Relations." Indagationes Mathematicae 13, 369 bis 373.
5. Erdős, P. und Rényi, A. (1963). "Asymmetric Graphs." Acta Mathematica Academiae Scientiarum Hungaricae 14, 295 bis 315. Enthält die Beobachtung, dass der abzählbare Zufallsgraph bis auf Isomorphie eindeutig bestimmt ist.
6. Halin, R. (1964). "Über unendliche Wege in Graphen." Mathematische Annalen 157, 125 bis 137. Die Theorie der Enden von Graphen.
7. Rado, R. (1964). "Universal Graphs and Universal Functions." Acta Arithmetica 9, 331 bis 340. Die explizite Konstruktion des universellen abzählbaren Graphen.
8. Cameron, P. J. (1997). "The Random Graph." In R. L. Graham und J. Nešetřil (Hrsg.), The Mathematics of Paul Erdős II, 333 bis 351. Berlin: Springer. Ein Überblick über den Rado-Graphen und seine Eigenschaften.
9. Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics 184. New York: Springer.
10. West, D. B. (2001). Introduction to Graph Theory, 2. Auflage. Upper Saddle River: Prentice Hall.
11. Bondy, J. A. und Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer.
12. Diestel, R. (2017). Graph Theory, 5. Auflage. Graduate Texts in Mathematics 173. Berlin: Springer. Kapitel 8 ist unendlichen Graphen, Strahlen und Enden gewidmet.