Ends of graphs
Maya Stein · 2005
Our topic is infinite graph theory, with our focus on the ends of an infinite graph (which can be informally viewed as endpoints of rays), and their role in extensions of results known for finite graphs. Often, these extensions fail, if one does not take into account the ends of the graph, but otherwise hold. In other cases, results become more interesting when ends are considered as well as vertices. An example for the latter is the Erdos-Menger conjecture for infinite graphs (recently proved by Aharoni and Berger): we shall prove a generalization which allows for ends in the considered paths and separators. This means that in an infinite graph, we allow paths to be infinite. Moreover, considering ends on a par with vertices, we will allow these paths, then called arcs, to start or end in ends, and to pass through them. Similarly, the notion of a cycle will be generalized to that of a (possibly infinite) circle, which may pass through ends. This leads to a different notion of forests (so-called topological forests) in infinite graphs. Another aspect of the ends is that since in many ways they behave like vertices, they should be attributed a degree. We introduce such a notion as well as a concept of parity for ends. For ends of finite degree the parity will coincide with the parity of the degree, while ends of infinite degree will be classified into ‘even’ and ‘odd’. Using these concepts (arcs, circles, topological forests, degrees and parities of ends) we extend several results from finite graph theory verbatim to infinite graphs. Die vorliegende Arbeit behandelt Themen der unendlichen Graphentheorie. Im Mittelpunkt stehen dabei die Enden eines Graphen. Unter Einbeziehung der Enden lassen sich Resultate der endlichen Graphentheorie auf unendliche Graphen ubertragen, die andernfalls scheitern. Auch in anderen Fallen lohnt es, die Ecken und Enden eines unendlichen Graphen als gleichberechtigt zu betrachten. Wir erlauben daher unendliche Wege und unendliche Kreise, die durch Enden ’hindurchlaufen’: genauer gesagt sind dies homoomorphe Bilder des Einheitsintervalls bzw. des Einheitskreises, unter Verwendung der naturlichen Topologie auf dem Graphen zusammen mit seinen Enden (fur lokal endliche Graphen ist dies deren Freudenthal-Kompaktifizierung). Unendliche Kreise und der daraus resultierende Zyklenraum C(G) unendlicher Graphen wurden von Diestel und Kuhn eingefuhrt. Analog zum Gradbegriff fur Ecken entwickeln wir einen Gradbegriff fur Enden, der globale Forderungen wie z.B. hohen Minimalgrad auch fur unendliche Graphen erlaubt. Desweiteren definieren wir die Paritat bei unendlichen Grad. Diese Anpassungen der Standardbegriffe ermoglichen die wortwortliche Ubertragung folgender Ergebnisse auf unendliche Graphen: • Charakterisierung der Graphen G, bei denen E(G) Element des Zyklenraums C(G) ist, als solche, die uberall geraden Grad haben, • Erzwingung hochzusammenhangender Teilgraphen durch hohen Minimalgrad (im Endlichen ein Satz von Mader), • Nash-Williams’ Arborizitatssatz (allerdings mit einer zusatzlichen Beschrankung des Endengrades), • Gallai’s Satz, • MacLane’s Plattbarkeitskriterium, • Erzeugung des Zyklenraums durch lange Kreise (Locke). Eines der wichtigsten Resultate ist • Die Endenversion der Erdos-Menger Vermutung. Diese bekannte Vermutung von Erdos erweitert den Satz von Menger auf unendliche Graphen, und ist in der Eckenversion kurzlich von Aharoni und Berger bewiesen worden. In der Endenversion sind neben Ecken auch Enden in den zu verbindenden Mengen sowie dem Trenner erlaubt.