I was inspired to add a Wikipedia article on ends of infinite graphs after learning that an end is essentially the same thing as a haven, a construction with a very different use in finite graph theory (characterizing treewidth). As a warm-up exercise on working with ends, I thought I'd generalize the oldest lemma in graph theory, the handshaking lemma stating that every finite graph has an even number of odd-degree vertices.

To begin, let's define what it means for an end to be odd. If \( X \) is a finite set of vertices in a locally finite graph (one in which every vertex has finite degree) then every \( X \)-flap (connected component of the complement of \( X \)) has a finite number of edges connecting it to the rest of the graph, and we can define the parity of the flap to be the parity of this set of edges. We'll say that an end is odd if the corresponding haven \( \beta \) has the property that every finite \( X \) has a finite superset \( Y \) for which the \( Y \)-flap \( \beta(Y) \) is odd.

Lemma: In a locally finite graph, every odd flap contains an odd end or an odd vertex.

Proof sketch: Let \( F \) be an odd \( X \)-flap of the given graph \( G \) and define a sequence of finite sets \( X_i \) to be the set of vertices at distance at most \( i \) from \( X. \) We will define a nested sequence of odd flaps for these vertices, starting with \( F_0 = F. \) If \( F_i \) is an odd flap already defined in this way, let \( Y_i \) be the intersection of \( F_i \) with \( X_{i+1}, \) and form a finite graph \( G_i \) by contracting \( X_i \) and each \( Y_i \)-flap inside \( F_i \) to a single vertex. Then the vertex of \( G_i \) formed by contracting \( X_i \) is odd, by the assumption that \( F_i \) is an odd flap, so by the handshaking lemma for finite graphs \( G_i \) must have another odd vertex. If this second odd vertex is in \( Y_i, \) it is a vertex of \( G \) inside \( F, \) proving the lemma. Otherwise, it is an odd flap, which we select as \( F_{i+1}. \) Thus, this process either terminates or it produces an infinite sequence of odd flaps. In the latter case it can be used to define an odd haven \( \beta \) in which \( \beta(Z) \) is calculated by finding \( i \) large enough that \( X_i \) contains \( Z \) and choosing the \( Z \)-flap containing \( F_i. \)

Theorem: If a locally finite graph has a finite number of odd vertices and odd ends, that number is even.

Proof sketch: let \( X \) be a finite set that contains all the odd vertices of the given graph \( G \) and that separates all the odd ends from each other. For the \( i \)th odd end, defined by haven \( \beta_i \), choose \( Y_i \) to be a superset of \( X \) for which \( \beta_i(Y_i) \) is odd; we may assume without loss of generality that \( Y_i \setminus X \) is contained within \( \beta_i(X), \) because any vertices outside this set do not change the \( Y_i \)-flap selected by \( \beta_i. \) Let \( Y \) be the union of the sets \( Y_i, \) and form a finite graph \( H \) whose vertices are \( Y \) and all of the \( Y \)-flaps of \( G. \) Then by the handshaking lemma for finite graphs \( Y \) has an even number of odd vertices, each of which is either an odd vertex of \( G \) or a flap containing a single odd end.

Euler used the handshaking lemma to characterize the finite graphs that have Euler paths and Euler tours. An infinite graph cannot have an Euler tour (a cycle is always finite) but may have an Euler path. The correct characterization seems to be that a connected locally finite graph has a doubly-infinite Euler path if and only if there is no odd vertex and either a single even end or two odd ends (but not both!) and has a singly-infinite Euler path if and only if there is an odd vertex, a single odd end, and no even ends. If so, I think Erdos, Grünwald, and Vásonyi 1938 is the correct reference, but unfortunately I can't read German to tell for sure what's in that paper or whether it even has a clear concept of an end of a graph. (There have also been several papers on topological Euler tours in the end compactification of a locally finite graph [1,2], which is not quite the same thing.)




Comments:

ext_921097: Also interesting news from today:
2011-12-09T04:15:40Z

The 2011 ACM fellows were announced. Congratulations!

http://fellows.acm.org/homepage.cfm

11011110: Re: Also interesting news from today:
2011-12-09T05:08:50Z
Thanks!