Part III · The Deep Theory

Chapter 8: Infinite Graphs

Created by Felipe Casadei

Every graph so far had finitely many dots and lines. This chapter lets a graph run on forever, teaches the three proof tools that keep infinity under control, and introduces something genuinely new: the ends of a graph, its points at infinity.

What changes when a graph never ends

Picture the natural numbers \(0, 1, 2, 3, \ldots\) as dots, with a line between each number and the next. Or picture the street corners of a city whose grid of streets extends forever north and forever east. These are perfectly ordinary graphs in the sense of Chapter 1: a set of vertices, a set of edges, each edge joining two vertices. Nothing in the definition ever said the sets had to be finite.

Almost all the vocabulary survives unchanged: degrees, paths, trees, connectedness, colourings all mean what they meant before. What changes is the reasoning. A finite argument often works by repeating a step until the vertices run out; in an infinite graph they never do, and a construction that looks fine at every step can still produce garbage in the limit. The first half of this chapter teaches the three standard tools that repair this: Zorn's lemma, transfinite induction, and compactness. The second half is about a concept with no finite counterpart at all: the ends of a graph, the distinct directions in which one can walk to infinity.

Two pieces of vocabulary first. Throughout the chapter, "countable" means finite or as large as the set \(\mathbb{N}\) of natural numbers, and \(\aleph_0\) (read "aleph-nought") is the size of \(\mathbb{N}\): the smallest infinite size. The complete graph on countably many vertices is written \(K^{\aleph_0}\). (Diestel writes complete graphs with a superscript, \(K^n\) and \(K^{\aleph_0}\); many other books write \(K_n\).)

Local finiteness separates the two kinds of infinity a graph can have: being infinitely long (containing rays) and being infinitely wide (containing a vertex of infinite degree). Most of the cleanest theory in this chapter, especially the topological second half, is about locally finite graphs, where only the "long" kind occurs.

New notation in this chapter

Three symbols get recycled with new meanings here, so read this table carefully: in this chapter \(|G|\) and \(\|G\|\) are topological spaces (not the order and size of \(G\) from Chapter 1), and the letter \(\omega\) names an end (not the clique number).

Three tools for taming infinity

Why do we need new tools at all? Take the most innocent statement imaginable: every connected graph has a spanning tree, a cycle-free connected subgraph containing every vertex. The finite proof grows the tree one vertex at a time and stops when the vertices are used up. In an infinite graph that procedure never stops, so the proof says nothing. The statement is still true^[1], but each of its proofs demonstrates one of the chapter's tools.

Tool 1: Zorn's lemma. Instead of building the object step by step, grab a maximal one all at once. Zorn's lemma says: in a partially ordered collection, if every chain (totally ordered sub-collection) has an upper bound in the collection, the collection has a maximal element. For spanning trees, order all trees inside \(G\) by inclusion. A chain of trees has an upper bound, its union: any cycle in the union would be finite, hence would already lie inside one single tree of the chain. Zorn hands us a maximal tree, which must reach every vertex (a missed vertex adjacent to the tree could be added). Note where finiteness of cycles did the real work: it made the limit safe.

Tool 2: transfinite induction. Keep the step-by-step construction, but let it continue past infinity, with ordinal numbers as the clock: after steps \(0, 1, 2, \ldots\) comes a limit step, then further steps beyond it. At ordinary steps you add a vertex; at limit steps you take the union of everything so far, and again finiteness of cycles makes the unions safe. The formal machinery of ordinals lives in Diestel's Appendix A^[9]; the mental picture "step-by-step, with union steps sprinkled in" is enough for this course.

Tool 3: compactness. Solve the problem on every finite piece, then glue the finite solutions into one infinite solution. This is the tool with the biggest payoff, and its graph-theoretic engine is a lemma of Dénes Kőnig.

Read it as a picture: an infinite stack of finite levels, each pointing back into the previous one, always contains one infinite thread. Proof idea: walk backwards along the pointers from every vertex. Since \(V_0\) is finite, infinitely many of these backward walks land on the same vertex of \(V_0\); among those, infinitely many agree on their \(V_1\) vertex too, and so on. The choices that survive every round form the ray. Finiteness of the levels is essential: with even one infinite level the conclusion can fail.

Here is compactness earning its keep. Recall from Chapter 5 that the chromatic number \(\chi(G)\) is the least number of colours needed to colour the vertices so that adjacent vertices get different colours.

Proof idea via the Infinity Lemma, for countable \(G\): enumerate the vertices and let \(V_n\) be the set of proper \(k\)-colourings of the first \(n\) vertices: finite (at most \(k^n\)) and non-empty by hypothesis, with restriction as the backward pointer. A ray through the levels is a coherent family of colourings that together colour every vertex. Diestel gives two further proofs, via an abstract compactness principle and via Tychonoff's theorem from topology; all three are the same idea in different clothes.^[1]

One warning keeps compactness honest: sometimes the finite statement must be reshaped before it can pass to the limit. The chapter's showcase is the unfriendly partition conjecture: every countable graph should admit a split of its vertices into two camps such that every vertex has at least as many neighbours in the other camp as in its own. Finite graphs are easy: take the split with the most cross-edges; a vertex with more friends than enemies could profitably defect. For infinite graphs "most cross-edges" makes no sense, and the conjecture is open for countable graphs in general. The book proves it for locally finite graphs, by an Infinity Lemma argument that deliberately weakens the requirement at each finite stage, and for countable rayless graphs in Section 8.5; for some uncountable graphs it fails.^[1]

Ends: the points at infinity

Now for the genuinely new idea. Watch someone walk forever along a ray in the two-way infinite ladder (two parallel double rays joined by rungs). Eventually they drift off to the left, or off to the right. No matter how the ray wiggles between the rails, one of those two fates awaits it. The ladder has, in a sense we can now make precise, exactly two points at infinity. In the endless street grid, by contrast, all escapes lead to the same place: delete any finite set of corners and the remaining infinite part is still one connected piece, so any two rays can always be re-joined beyond the deletion. One graph, one point at infinity.

To define this precisely we first need the right notion of "an infinite set of vertices accumulating in some direction," and for that Diestel uses a charming object called a comb.

Convince yourself that this is an equivalence relation, and notice what it does not depend on: where the rays start, or whether they share any vertices. Two disjoint rays can point to the same end (any two vertical rays of the grid do), and equivalent rays can always be joined to each other by infinitely many disjoint paths. The definition captures where a ray goes, not how it gets there.

How many ends can a graph have? The double ray has two, the grid has one, and here is the surprise: a countable, locally finite tree can have as many ends as there are real numbers. Consider the binary tree \(T_2\), whose vertices are the finite strings of 0s and 1s, with each string \(s\) joined to \(s0\) and \(s1\). A ray from the root is exactly an infinite 0–1 sequence, read digit by digit. In a tree, two rays are equivalent only if they eventually merge (deleting the last common vertex separates them otherwise), so distinct infinite sequences give distinct ends. There are uncountably many infinite 0–1 sequences, so \(T_2\) has uncountably many ends: continuum many points at infinity attached to countably many vertices.^[1]

Ends come in different widths. The vertex-degree of an end \(\omega\) is the maximum number of pairwise disjoint rays belonging to \(\omega\); the edge-degree is the same with "edge-disjoint" in place of "disjoint." Both values live in \(\mathbb{N} \cup \{\infty\}\), and it is a theorem, not an observation, that the maximum is actually attained (more on this below). An end of infinite vertex-degree is called thick; an end of finite vertex-degree is thin. Each end of the ladder is thin, with vertex-degree 2: the two rails are disjoint rays, and any three rays going the same way would need to squeeze through rungs of width 2. The single end of the grid is thick: the vertical lines are infinitely many disjoint rays, all equivalent.^[1]

Long or wide: paths, trees, and ends

The first structural theorem of the chapter says that the two kinds of infinity we identified are the only ones. Every infinite connected graph contains a ray or a vertex of infinite degree (and if it is locally finite, therefore a ray).^[2] Proof idea: fix a vertex and sort all other vertices into classes by their distance from it. If all degrees are finite, each distance class is finite and non-empty; each vertex at distance \(n\) has a neighbour at distance \(n-1\), and König's Infinity Lemma threads a ray through the classes. The Star–Comb Lemma refines this dichotomy from graphs to vertex sets:

In plain words: an infinite crowd of vertices must either string out along some ray (the comb catches infinitely many of them along one direction to infinity) or cluster around a single hub (the star's centre reaches infinitely many of them by disjoint paths). In a locally finite graph the star is impossible, so infinite vertex sets always point at an end. This little lemma is the standard bridge between "a set of vertices" and "a direction at infinity," and it will reappear in the topological sections.

Next, a structural tool that tames the potentially wild set of ends. Recall from Chapter 1 that a rooted spanning tree \(T\) of \(G\) is normal if the endpoints of every edge of \(G\) not in \(T\) are comparable in the tree order (one lies on the root-path of the other). Normal spanning trees organize a finite graph beautifully, and the same is true at infinity, where the branches climbing up from the root become normal rays.

So a normal spanning tree is a perfect catalogue: one root-based branch per point at infinity. The existence half imitates the finite construction, growing finite normal trees \(T_0 \subseteq T_1 \subseteq \cdots\) that swallow the vertices in some fixed enumeration, with care taken so that each new branch is grafted at the top of the relevant part of the tree order. Countability matters: the uncountable complete graph has no normal spanning tree. Diestel calls normal spanning trees the single most important structural tool of infinite graph theory, and Section 8.6 will convert that praise into a theorem: they characterize exactly when the space \(|G|\) can be given a metric.

Now for one of the chapter's celebrated results. Say you know that your graph contains \(k\) pairwise disjoint rays for every natural number \(k\): 5 disjoint rays, 500, 5 million, as many as you ever ask for. Must it contain infinitely many disjoint rays at once? Be careful: this is not a triviality. A single badly chosen ray can wander everywhere and block all others, so you cannot just greedily pick rays one at a time. For general structures the answer is no; graphs \(H\) exist for which arbitrarily many disjoint copies do not force infinitely many. Halin proved that for rays the answer is yes.

Proof idea: build the infinite family in infinitely many rounds. At round \(n+1\), take a fresh supply of very many disjoint rays, discard the few that collide with the finite initial segments frozen so far, and use Menger's theorem from Chapter 3 (the finite max-paths-equals-min-separator theorem) inside a well-chosen finite auxiliary graph to reroute the current \(n\) rays plus one newcomer so that all of them extend their frozen initial segments. The actual infinite rays exist only in the limit, but each vertex's fate is sealed at some finite round, so the limit is safe. This argument is also what guarantees that the vertex-degree of an end is attained as a maximum, so "thick" and "thin" are well defined.

The general phenomenon has a name: call a graph \(H\) ubiquitous with respect to a containment relation (subgraph, minor, and so on) if, whenever a graph contains \(n\) disjoint copies of \(H\) for every \(n\), written \(nH\), it contains \(\aleph_0 H\), countably many disjoint copies. Halin's theorem says the ray is ubiquitous for the subgraph relation. Andreae's Ubiquity Conjecture, still open, asserts that every locally finite connected graph is ubiquitous with respect to the minor relation.^[2]

Halin also proved that thickness has a canonical shape. The hexagonal quarter grid \(H^\infty\) is what you get by carving a brick-wall pattern out of the quarter-plane grid: infinitely many vertical rays, joined by horizontal edges in alternating positions, so that every vertex has degree at most 3.

In plain words: an end with infinitely many parallel lanes to infinity always organizes itself into a grid. (Hexagonal rather than square because a subdivision, which must respect degrees, can only be found for a target graph of small maximum degree; and the ordinary grid is a minor of \(H^\infty\), so nothing is lost.) The proof repeatedly picks a new "vertical" ray and infinitely many disjoint "horizontal" connecting paths to the previous verticals, exploiting the fact that rays in a common end can always be linked by infinitely many disjoint paths; König's Infinity Lemma then organizes the connection pattern into the grid. Readers who go on to Chapter 12 will recognize this as the infinite ancestor of the excluded-grid theme in the theory of graph minors.

The Rado graph: one graph to contain them all

Infinite graphs make possible a kind of object that simply cannot exist in the finite world: a single countable graph that contains every countable graph. Call a countable graph \(G^\ast\) universal (for a fixed containment relation, within a class of graphs) if every countable graph in the class is contained in \(G^\ast\) under that relation. For the induced-subgraph relation and the class of all countable graphs, a universal graph exists, it is unique, and it is wonderful. Its defining feature is the extension property we met in the notation table:

Existence is brute force: start with one vertex, and at each stage add, for every subset \(U\) of the vertices built so far, one new vertex joined to exactly \(U\); iterate forever. Uniqueness is the classic back-and-forth argument: given two graphs with \((\ast)\), build an isomorphism vertex by vertex, alternating sides. At each step the next unmatched vertex on the current side has some finite pattern of adjacencies to the already-matched vertices, and \((\ast)\) on the other side supplies a partner realizing exactly that pattern. Alternating sides guarantees no vertex is left behind, so the final map is an isomorphism of the whole graphs. And universality falls out of the same idea run on one side only: to embed an arbitrary countable graph \(H\) into \(R\) as an induced subgraph, add the vertices of \(H\) one at a time, using \((\ast)\) to realize each one's adjacency pattern to its predecessors.

\(R\) is called the Rado graph, and it has a habit of shrugging off damage: delete any finite set of vertices, or flip any finite set of edges and non-edges, and the resulting graph still satisfies \((\ast)\), so it is again isomorphic to \(R\). Stronger still, however you split the vertices of \(R\) into two parts, at least one part induces a copy of \(R\); and \(R\) is essentially the only countable graph with that self-reproducing property.^[3]

The Rado graph is also as symmetric as a countable graph can be: it is homogeneous, meaning every isomorphism between two finite induced subgraphs extends to an automorphism of the whole graph. Any local identification globalizes. Homogeneity is so demanding that all countable homogeneous graphs are known: by the classification of Lachlan and Woodrow, they are the disjoint unions of complete graphs of one size and their complements, the generic \(K^r\)-free graphs \(R^r\) (Rado-like constructions that never build a complete graph on \(r\) vertices) and their complements, and \(R\) itself.^[3] The classification's proof is beyond this course and the book alike.

Universality depends delicately on the containment relation. For the subgraph or induced-subgraph relation there is no universal planar graph, but Diestel and Kühn proved that a universal planar graph does exist for the minor relation^[3]: one countable planar graph containing every countable planar graph as a minor. Same class of graphs, different relation, opposite answer.

Connectivity and matching without counting

The deepest part of the chapter asks what becomes of the great min-max theorems of Part II: Menger's theorem from Chapter 3 and the matching theorems of Chapter 2. The lesson, learned slowly over fifty years, is that for infinite graphs counting is too blunt an instrument, and every one of these theorems must be restated structurally before it becomes true and interesting again.

See the problem in the case of Menger. The finite theorem says: for vertex sets \(A\) and \(B\), the maximum number of disjoint \(A\)–\(B\) paths equals the minimum number of vertices needed to separate \(A\) from \(B\). Read with infinite cardinalities, this equality is true but worthless. Take any inclusion-maximal set \(\mathcal{P}\) of disjoint \(A\)–\(B\) paths (Zorn's lemma provides one). The union of all vertices of those paths separates \(A\) from \(B\), since any path avoiding it could be added to \(\mathcal{P}\). And when \(\mathcal{P}\) is infinite, that union has the same cardinality as \(\mathcal{P}\) itself: infinitely many paths have infinitely many vertices, but no more in cardinal arithmetic. So "max paths = min separator" holds for silly reasons, while enormously wasteful separators pass the test unnoticed. Erdős proposed the right fix: ask for a separator that is not merely small but efficient, using exactly one vertex from each path. After half a century as the Erdős–Menger conjecture, this became:

For finite graphs this is equivalent to Menger's theorem. For infinite graphs it is the correct statement, and it is hard: the book proves the countable case in full, over several pages, and the general case (which also covers ends and edge-versions) is one of the deepest results in the book. The central device of the proof is the wave.

Why waves rather than the augmenting-path arguments of Chapter 2? Because iterating augmentations can toggle one edge in and out forever, so the sequence of improvements has no meaningful limit. Waves fix this: they grow all paths simultaneously, they are partially ordered in a way where every chain of waves has a limit wave, and Zorn's lemma therefore supplies a maximal wave. Its boundary is a minimal separator, and the heart of the proof is showing, vertex by delicate vertex, that when no further progress by waves is possible, every boundary vertex can be linked onward to \(B\) without stranding the others. The full argument is in Section 8.4 of the book^[4]; it is honest to say it is the hardest proof in this course's orbit, and we only wave at it from the shore.

The same "structure instead of counting" philosophy rebuilt all of matching theory. Three highlights, in increasing depth:

Second highlight: Hall's marriage theorem. The finite condition from Chapter 2, "every set \(S \subseteq A\) has at least \(|S|\) neighbours," is nearly meaningless for infinite sets: an infinite \(S\) with an infinite neighbourhood \(N(S)\) passes the size test even when a matching is clearly impossible. The correct infinite bookkeeping uses matchability: say \(X\) is matchable to \(Y\) if the graph between them has a matching covering all of \(X\). Aharoni's infinite marriage theorem then reads: a bipartite graph has a matching of \(A\) unless some \(S \subseteq A\) is not matchable to \(N(S)\) while \(N(S)\) is matchable to \(S\).^[4] That asymmetric pair of conditions is the structural translation of "\(S\) is strictly bigger than its neighbourhood," and it survives infinity. Behind it stands an infinite König duality theorem in exactly the Erdős–Menger style: every bipartite graph has a matching \(M\) and a vertex cover using exactly one vertex of every edge of \(M\).

Third highlight: 1-factors of arbitrary graphs. For countable graphs, Steffens proved the clean criterion: a 1-factor exists if and only if, for every matching \(M\) and every vertex that \(M\) leaves uncovered, some \(M\)-augmenting path starts there, where an augmenting path is now allowed to be an infinite ray of alternating edges (swapping along an infinite alternating ray still matches every vertex on it).^[4] For arbitrary cardinalities, Aharoni found the Tutte-type condition: \(G\) has a 1-factor if and only if, for every vertex set \(S\), the factor-critical components of \(G - S\) are matchable to \(S\) in the natural auxiliary bipartite graph. Notice the pattern one more time: the finite theorem's number comparison (odd components versus \(|S|\), from Tutte's theorem in Chapter 2) is replaced by a matchability statement. The section closes with an infinite Gallai–Edmonds structure theorem obtained from a maximal such pair, and with the Aharoni–Korman conjecture on infinite perfect graphs, still open.^[4]

One more result of this section deserves its plain-words statement, because it is beautiful and its proof style is instructive: a graph decomposes into edge-disjoint cycles if and only if it has no odd cut, a cut with a finite, odd number of edges (Nash-Williams). Cycles cross every cut an even number of times, so odd cuts are an obvious obstruction; the theorem says they are the only one. The proof first chops the graph, however uncountable, into countable pieces that respect all small cuts (Laviolette's bond-faithful decomposition), then handles a countable graph by enumerating edges and repeatedly deleting a cycle through the first surviving edge.^[4]

Induction past infinity: recursive structures

Finite graph theory leans constantly on induction: prove the statement for small graphs, then reduce big ones to smaller ones. Section 8.5 shows how to salvage induction for infinite graphs by defining graph classes recursively, so that each infinite object is built from strictly simpler ones, with ordinals keeping score.^[5]

Two examples. First, call a rooted tree recursively prunable if the following labelling process eventually labels every vertex: at each stage, label those vertices whose set of unlabelled ancestors-and-descendants above them forms a single chain (intuitively: repeatedly shave off the simple, path-like fringe). Proposition 8.5.1: a rooted tree is recursively prunable exactly when it contains no subdivision of the binary tree \(T_2\). Infinite binary branching is precisely what pruning can never exhaust.

Second, and more important: the rank of rayless graphs. Finite graphs have rank 0; a graph has rank \(\alpha\) if it has no smaller rank and some finite vertex set \(U\) exists such that every component of \(G - U\) has rank smaller than \(\alpha\). For instance, a star with infinitely many finite paths of unbounded lengths attached has rank 1: delete the hub (a finite set) and only finite components remain. Lemma 8.5.2: a graph has a rank if and only if it contains no ray. So the rayless graphs form a hierarchy indexed by ordinals, and one can do induction on rank. The section's payoff theorem: every countable rayless graph has an unfriendly partition, proved by exactly such an induction, carefully stitching together partitions of the components of \(G - U\).^[5] (The result extends to rayless graphs of any cardinality, by Bruhn, Diestel, Georgakopoulos and Sprüssel.)

The space \(|G|\): where rays arrive

Everything so far treated ends combinatorially. The last three sections of the chapter make a bolder move: they turn the graph and its ends into a single topological space, in which rays literally converge to their ends the way the sequence \(1, \frac{1}{2}, \frac{1}{4}, \ldots\) converges to 0. The reward is remarkable: several classical theorems that are false for infinite graphs when read naively become true again, in their original wording, once "path," "cycle," and "spanning tree" are reinterpreted topologically.

The construction, denoted \(|G|\), works like this. Draw \(G\) with every edge as a real unit-length segment: the points of the space are the vertices, the interior points \(\mathring e\) of every edge \(e\), and one new point for each end. Near vertices and inside edges, "close" means what it looks like. Near an end \(\omega\), closeness is measured by roadblocks: a basic neighbourhood of \(\omega\) is chosen by picking a finite vertex set \(S\) and taking everything beyond \(S\) in \(\omega\)'s direction: the component \(C(S, \omega)\) of \(G - S\) that contains tails of \(\omega\)'s rays, together with all ends living in that component and the inner initial pieces of the edges entering it. A ray in \(\omega\) eventually enters every such neighbourhood, so it converges to \(\omega\), just as intended. For \(G\) a ray, \(|G|\) is a closed interval: the ray plus one endpoint at infinity. This space is known in topology as the Freudenthal compactification.^[6]

Compactness is the whole point: every infinite journey in \(|G|\) now has a destination. This is the licence for all the limit constructions that follow. A companion theorem determines when the space is metrizable, that is, when its topology comes from an honest distance function: \(|G|\) is metrizable exactly when \(G\) has a normal spanning tree (and, by a 2020 theorem of Pitz resolving a conjecture of Halin, exactly when all minors of \(G\) have countable colouring number).^[6] The chapter's earlier hero thus returns with a purely topological job description.

Inside \(|G|\) we can now say what infinite paths and cycles should always have been. An arc is a homeomorphic copy of the closed interval \([0,1]\); a circle is a homeomorphic copy of the round circle; the circuit of a circle is the set of edges it traverses. A double ray whose two tails belong to two different ends forms an arc between those ends. A double ray whose two tails belong to the same end closes up through that end into a circle: an infinite cycle. Circles can be far wilder than that: the book constructs a "wild circle" in a graph built on the binary tree, a genuine topological circle passing through uncountably many ends.^[6] Yet arcs are not lawless. The key discipline is:

In plain words: finite cuts behave classically and cannot be jumped; infinite cuts can be jumped at infinity. This lemma marks the exact frontier between combinatorics and topology, and it is the reason parity arguments over finite cuts survive into the next section.

Now the payoff notion. A topological spanning tree of \(G\) is a standard subspace of \(|G|\) (the closure \(\overline H\) of some subgraph \(H\), meaning \(H\) plus every end it approaches) that is connected, contains every vertex, and contains no circle. This differs from an ordinary spanning tree in both directions, and the 1-way ladder shows how:

Both directions of the mismatch occur. An ordinary spanning tree can close a circle through an end, as \(T_2\) just did. And a topological spanning tree need not be connected as a graph: in the grid of Figure 8.6, the set of all vertical rays is a disconnected graph, but its closure (all vertical rays plus the single end, where they all meet) is connected, contains every vertex, and has no circle: a perfectly good topological spanning tree, held together only at infinity. The workhorse lemmas of the section say that for standard subspaces topological connectedness coincides with arc-connectedness, and can be tested by a purely finite criterion: a standard subspace is connected exactly when it has an edge in every finite cut of \(G\) whose two sides it meets. Also, closures of normal spanning trees are always topological spanning trees.^[6]

Why go to all this trouble? Because it repairs broken theorems. The tree packing theorem of Nash-Williams and Tutte (Chapter 2) says a finite multigraph has \(k\) edge-disjoint spanning trees if and only if every partition of its vertex set into \(\ell\) parts is crossed by at least \(k(\ell - 1)\) edges. Read with ordinary spanning trees, this is false for infinite graphs: there are locally finite counterexamples of arbitrarily high edge-connectivity. Read with topological spanning trees, it is true verbatim:

The proof runs the finite theorem on finite contractions of \(G\), threads the finite solutions together with König's Infinity Lemma, and uses the finite-cut criterion to verify that the limit subspaces are connected. It is the flagship demonstration of the chapter's motto: the topological viewpoint restores the finite theory.

The topological cycle space

With circles in hand we can rebuild the cycle space. Recall from Chapter 1 that the cycle space of a finite graph consists of all edge sets obtainable by adding cycles mod 2, addition being symmetric difference: an edge belongs to a sum when it belongs to an odd number of summands. To make infinite sums meaningful, only one restriction is needed: call a family of edge sets thin if no edge appears in infinitely many members; then each edge is voted on finitely often, and its membership in the thin sum is well defined. The topological cycle space \(\mathcal{C}(G)\) is the set of all thin sums of circuits, where circuits are edge sets of circles in \(|G|\) and may be infinite.^[7]

Given a topological spanning tree \(T\), the finite theory's chord-and-cut duality carries over. Each chord \(e\) (an edge outside \(T\)) closes a unique circle, whose circuit is the fundamental circuit \(C_e\); each tree edge \(f\) splits \(T\) into two arc-components, and the edges between them form the fundamental cut \(D_f\). The pleasant surprise, courtesy of the Jumping Arc Lemma: every fundamental cut is finite, even though fundamental circuits may be infinite. That finiteness is exactly what makes the following characterization legal:

Three consequences round out the theory: \(\mathcal{C}(G)\) is generated by the finite circuits alone (every element is a thin sum of them); every element of \(\mathcal{C}(G)\) is a disjoint union of circuits; and \(\mathcal{C}(G)\) is closed under thin sums, so infinitely many legal additions never lead out of the space.^[7] The middle statement is the hard one, proved by the limit technology of the next section, and it reconstructs even the wild circle from parity data alone.

Infinite graphs as limits of finite ones

The final section explains why the topological programme works so smoothly: the space \(|G|\) literally is a limit of finite graphs. The formal gadget is the inverse limit. Take a directed partially ordered set (any two elements have a common upper bound); attach to each element \(p\) a compact space \(X_p\); and for \(q\) above \(p\) give a continuous bonding map from \(X_q\) to \(X_p\), compatibly. The inverse limit \(\varprojlim (X_p)\) is the set of all consistent choices of one point from every \(X_p\), where "consistent" means the bonding maps carry each choice to the next. A fundamental lemma says: an inverse limit of non-empty compact spaces is non-empty and compact. König's Infinity Lemma is precisely the special case of finite sets indexed by \(\mathbb{N}\), so this section is compactness coming full circle.^[8]

For a graph \(G\), the finite views are its contractions: for each partition \(p\) of \(V(G)\) into finitely many classes with only finitely many edges between different classes, collapse each class to a single vertex, getting a finite multigraph \(G/p\). Partitions refine one another, refinement makes the collection directed, and coarsening gives the bonding maps between the spaces \(|G/p|\). The inverse limit of all these finite views is denoted \(\|G\|\).

In plain words: look at \(G\) through every possible finite lens at once; a point of the limit is a consistent answer to "where am I?" in every lens; and the space of all such answers is exactly the graph with its ends. Vertices and edge points are the answers that stabilize; ends are the answers that keep naming a collapsed "dummy" class in every view, the nested branches converging to infinity. Nothing about \(|G|\) is invented and nothing is lost.

The practical dividend is the lifting lemma: compatible objects in the finite views induce an object in the limit. Compatible families of finite paths yield arcs; compatible families of finite cycles yield circles; and compatible families of Hamilton cycles in the contractions yield a Hamilton circle: a circle in \(|G|\) through every vertex, and hence through every end. The two-way ladder shows the concept: its two outer double rays together with its two ends form a circle through all its vertices.^[8] Hamilton circles are the infinite reading of the Hamilton cycles studied in Chapter 10, and extending classical Hamiltonicity theorems to them is an active research frontier.

Where does the chapter leave us? With a working toolkit (Zorn, transfinite induction, compactness), a new geography (ends, thick and thin), one extraordinary object (the Rado graph, which returns as the countable random graph in Chapter 11), a hard-won philosophy (replace counting by structure, as in the Aharoni–Berger theorem), and a topological completion \(|G|\) in which the finite theory's broken theorems are whole again. The infinity lemma will be back at work in Chapter 9 on Ramsey theory, and the study of ends deepens into the theory of tangles in Chapter 12.