0xDE (11011110) wrote,

Odds and ends

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 β has the property that every finite X has a finite superset Y for which the Y-flap β(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 β in which β(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 ith odd end, defined by haven β_i, choose Y_i to be a superset of X for which β_i(Y_i) is odd; we may assume without loss of generality that Y_i \ X is contained within β_i(X), because any vertices outside this set do not change the (Y_i)-flap selected by β_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.)

Tags: graph theory, wikipedia
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded