Infinite circuits in locally finite graphs
Henning Bruhn · 2005
With the naive definition of the cycle space most of the theorems concerning the cycle space become false in infinite graphs. This is exemplified by Tutte's generating theorem, which states that the peripheral cycles generate the cycle space in a $3$-connected graph. To remedy this, Diestel and Kuhn proposed a topologically based definition of the cycle space, in which the circles are precisely the homeomorphic images of the unit circle in the Freudenthal compactification of the (locally finite) graph. This notion not only includes the traditional finite cycles but also allows for certain infinite cycles. In the course of this thesis, it is shown that the cycle space $\mathcal C(G)$ of Diestel and Kuhn is extremely fruitful and successful. Indeed, it is demonstrated that the classical theorems about the cycle space carry over to locally finite graphs either in a verbatim manner or with only slight but obvious adaptions. The current work extends the following theorems to locally finite graphs: the planarity criteria of MacLane and Kelmans (the first of which solves a problem of Wagner 1970); Whitney's planarity criterium and duality in terms of spanning trees; and Gallai's theorem. If infinite cycles are disallowed, all of these results either fail completely or have to be weakened considerably. In finite graphs, the elements of the cycle space are precisely those edge sets for which each vertex is incident with an even number of their edges. Such a characterisation, based solely on vertex degrees, becomes impossible in infinite graphs. Diestel and Kuhn asked whether the elements of the cycle space could nevertheless be described if additionally a suitable notion of an end degree was introduced. Such a notion is offered in the thesis, and an important special case of the full characterisation is proved: for every locally finite graph $G$ it holds that $E(G)\in\mathcal C(G)$ if and only if every vertex and every end has even degree. Furthermore, evidence is provided to substantiate the conjecture, that every locally finite $4$-connected planar graph has a Hamilton cycle. For finite graphs, this is a result by Tutte. Two other problems are addressed that are related to the cycle space. First, the question is pursued under which conditions there exists a minimal generating set, if infinite sums are allowed. Second, using the topology on which the cycle space is based on, certain special cases of the end version of the Erdos-Menger conjecture are proved. Mit der naiven Definition des Zyklenraums schlagen der uberwiegende Teil der Satze uber den Zyklenraum in unendlichen Graphen fehl. Ein Beispiel hierfur ist Tuttes Erzeugungssatz, der aussagt, dass die peripheren Kreise den Zyklenraum eines $3$-zusammenhangenden Graphen erzeugen. Diestel und Kuhn schlugen daher eine auf einem topologischen Ansatz basierende Definition vor, in der die Kreise gerade die homoomorphen Bilder des Einheitskreises in der Freudenthalkompaktifizierung eines lokal endlichen Graphen sind. Dieser Begriff schliest nicht nur die traditionellen endlichen Kreise ein, sondern erlaubt auch neuartige, unendliche Kreise. Im Verlauf dieser Arbeit wird dargelegt, dass der Zyklenraum $\mathcal C(G)$ von Diestel und Kuhn auserordentlich fruchtbar und erfolgreich ist. Es erweist sich, dass die klassischen Satze uber den Zyklenraum entweder wortliche oder geringfugig angepasste Entsprechungen in lokal endlichen Graphen haben. In der Arbeit werden die Plattbarkeitskriterien von MacLane und Kelmans (ersteres lost ein Problem von Wagner 1970); Whitneys Plattbarkeitskriterium und die Dualitat in Form von Spannbaumen; und Gallais Satz auf lokal endliche Graphen ubertragen. Werden unendliche Kreise nicht zugelassen, dann sind all diese Satze in lokal endlichen Graphen entweder falsch oder mussen zumindest erheblich abgeschwacht werden. Im Endlichen sind die Elemente des Zyklenraums gerade die Kantenmengen, fur die jede Ecke mit gerade vielen ihrer Kanten inzident ist. Im Unendlichen ist diese Charakterisierung allein durch Eckengrade nicht moglich. Diestel und Kuhn fragten, ob man dennoch die Elemente des Zyklenraums beschreiben kann, wenn zusatzlich ein geeigneter Gradbegriff fur Enden eingefuhrt wird. Ein solcher Begriff wird in der Arbeit vorgeschlagen und ein wichtiger Spezialfall der Charakterisierung bewiesen: fur einen lokal endlichen Graphen $G$ gilt, dass $E(G)\in\mathcal C(G)$ genau dann, wenn jede Ecke und jedes Ende geraden Grad hat. Desweiteren werden Indizien fur die Vermutung, dass jeder lokal endliche $4$-zusammenhangende plattbare Graph einen Hamiltonkreis besitzt, erbracht. Im Endlichen ist dies ein Satz von Tutte. Es werden noch zwei weitere Probleme betrachtet, die mit dem Zyklenraum in Verbindung stehen. Erstens wird untersucht, unter welchen Umstanden ein minimales Erzeugendensystem existiert, wenn unendliche Summen erlaubt sind. Zweitens wird die dem Zyklenraum zugrunde liegende Topologie verwandt, um gewisse Spezialfalle der Endenversion der Erdos-Menger-Vermutung zu beweisen.