Infinite circuits in locally finite graphs

Abstract

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 Kühn 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 Kühn 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 Kühn 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 Erdös-Menger conjecture are proved.

Mit der naiven Definition des Zyklenraums schlagen der überwiegende Teil der Sätze über den Zyklenraum in unendlichen Graphen fehl. Ein Beispiel hierfür ist Tuttes Erzeugungssatz, der aussagt, dass die peripheren Kreise den Zyklenraum eines $3$-zusammenhängenden Graphen erzeugen. Diestel und Kühn schlugen daher eine auf einem topologischen Ansatz basierende Definition vor, in der die Kreise gerade die homöomorphen Bilder des Einheitskreises in der Freudenthalkompaktifizierung eines lokal endlichen Graphen sind. Dieser Begriff schließt 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 Kühn außerordentlich fruchtbar und erfolgreich ist. Es erweist sich, dass die klassischen Sätze über den Zyklenraum entweder wörtliche oder geringfügig angepasste Entsprechungen in lokal endlichen Graphen haben. In der Arbeit werden die Plättbarkeitskriterien von MacLane und Kelmans (ersteres löst ein Problem von Wagner 1970); Whitneys Plättbarkeitskriterium und die Dualität in Form von Spannbäumen; und Gallais Satz auf lokal endliche Graphen übertragen. Werden unendliche Kreise nicht zugelassen, dann sind all diese Sätze in lokal endlichen Graphen entweder falsch oder müssen zumindest erheblich abgeschwächt werden.

Im Endlichen sind die Elemente des Zyklenraums gerade die Kantenmengen, für die jede Ecke mit gerade vielen ihrer Kanten inzident ist. Im Unendlichen ist diese Charakterisierung allein durch Eckengrade nicht möglich. Diestel und Kühn fragten, ob man dennoch die Elemente des Zyklenraums beschreiben kann, wenn zusätzlich ein geeigneter Gradbegriff für Enden eingeführt wird. Ein solcher Begriff wird in der Arbeit vorgeschlagen und ein wichtiger Spezialfall der Charakterisierung bewiesen: für 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 für die Vermutung, dass jeder lokal endliche $4$-zusammenhängende plättbare 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 Umständen ein minimales Erzeugendensystem existiert, wenn unendliche Summen erlaubt sind. Zweitens wird die dem Zyklenraum zugrunde liegende Topologie verwandt, um gewisse Spezialfälle der Endenversion der Erdös-Menger-Vermutung zu beweisen.