Orientations of infinite graphs

An orientation of an undirected graph is the directed graph that you get by assigning a direction to each edge. Several kinds of orientations have been studied. For instance, in a graph with even vertex degrees, an Eulerian orientation makes the numbers of incoming and outgoing degrees equal at each vertex. In a bridgeless graph, a strong orientation makes the resulting directed graph strongly connected. In finite connected graphs, every Eulerian orientation is strong, but that is untrue in infinite graphs. Consider, for instance, the graph of unit distances on the integers, which is Eulerian (every vertex has degree two) but has no strong orientation (every edge is a bridge). Even when a strong orientation exists, an Eulerian orientation might not be strong: the graph of distance-1 and distance-2 integers, with the orientation from smaller to larger numbers, is Eulerian but not strong. So when does an Eulerian strong orientation exist? The answer turns out to be: whenever the obvious obstacles are not present. Every bridgeless connected even-degree infinite graph has an Eulerian strong orientation.

To prove this, we can use a convenient tool for dealing with infinite orientations by looking only at finite graphs, a result of Rado from 1949 that is simultaneously a predecessor and generalization of the De Bruijn–Erdős theorem on graph colorings. Suppose each element in some infinite set \(S\) has a finite set of labels, and we choose an assignment of labels for each finite subset of \(S\). These choices may be inconsistent with each other, so there may be no way of labeling all of \(S\) consistently with all of the choices. But Rado proved (assuming the axiom of choice) that there exists a global labeling that, on every finite subset, is consistent with the assignment to one of its finite supersets. Another way of thinking about this is that if certain finite patterns must be avoided, and every finite subset has a labeling that avoids them, then some global labeling will also avoid them.¹ The De Bruijn–Erdős theorem is the case where the elements are vertices, the labels are colors, and the patterns to be avoided are pairs of equal color on adjacent vertices. In our case the set elements will be edges, the labels will be which way to orient each edge, and the choice of assignment will be some way of defining a “good” orientation for finite subgraphs.

So suppose we’re given a finite subgraph \(G\) of an infinite 2-edge-connected even-degree graph. What kind of orientation on \(G\) should we look for? A complication is that \(G\) might have bridges or odd-degree vertices. So we’ll try to come as close as we can to what we want, an Eulerian strong orientation, while taking those deficiencies into account. Let’s define a good orientation of \(G\) to be an orientation that is almost Eulerian, in that at each vertex the in-degree and out-degree differ by at most one, and almost strong, in that each edge of \(G\) that belongs to an undirected cycle also belongs to a directed cycle. Another way of stating the almost strong condition is that the strongly connected components of the oriented graph should coincide with the 2-edge-connected components, or blocks, of the undirected graph.

The existence of a good orientation of an arbitrary finite undirected graph (also having some other stronger properties) was proven in the 1960s by Nash-Williams.² But now Rado’s method proves that every infinite graph also has a good orientation. If we find a global orientation that’s nearly-Eulerian on a supergraph of the star of neighbors of every vertex, then it must be nearly-Eulerian. And if it’s almost strong on a supergraph of every cycle, then it must be almost strong. This proves the theorem that a bridgeless connected even-degree infinite graph has an Eulerian strong orientation, because every good orientation in these graphs must be Eulerian and strong. Nash-Williams already considered the infinite case of his orientation theorem, but wrote that the details were too heavy to include. Perhaps he didn’t know about Rado’s theorem (despite it being published in the same journal), which makes the extension from finite to infinite easy.

The same method of extending finite to infinite orientations can also be used to study notions of graph sparseness including arboricity, degeneracy, and pseudoarboricity. Historically the pseudoarboricity of infinite graphs was first. A graph has pseudoarboricity at most \(p\) if it can be oriented so that each vertex has out-degree \(p\) (or equivalently if it can be partitioned into subgraphs each with out-degree one). In the 1950 paper in which he first announced the De Bruijn–Erdős theorem, Erdős used it to prove that, when such an orientation is given, the resulting graph can be \((2k+1)\)-colored.³ But he didn’t write about the conditions under which such an orientation exists. Rado’s theorem shows that they are the same as in the finite case: an outdegree-\(p\) orientation exists if and only if every finite \(k\)-vertex subgraph has at most \(pk\) edges.

A graph has degeneracy at most \(d\) if it has an acyclic orientation so that each vertex has out-degree \(d\). Unlike in the finite case, infinite graphs with low degeneracy might have high minimum degree; for instance, there exist graphs with degeneracy one in which all vertices have infinite degree. A finite \(d\)-degenerate graph can be \((d+1)\)-colored greedily, and the De Bruijn–Erdős theorem shows that even in the infinite case such a coloring exists. Rado’s theorem shows that infinite graphs with pseudoarboricity \(p\) are \(2p\)-degenerate, and that a graph is \(d\)-degenerate if and only if every finite subgraph has a vertex with degree at most \(d\). As in the case of Eulerian strong orientations, this involves checking the orientation only on two kinds of finite subgraphs, stars and cycles.

Arboricity is based on forests and there are multiple incompatible definitions of infinite forests. But the one we want to use is that a forest is a 1-degenerate graph. A graph has arboricity \(a\) if its edges can be partitioned into \(a\) forests. This is clearly at least as large as the degeneracy (no Rado needed). Rado’s theorem shows that infinite graphs with arboricity \(a\) are \(2a-1\)-degenerate, and that a graph has arboricity at most \(a\) if and only if every finite \(k\)-vertex subset has at most \(a(k-1)\) edges.

(Discuss on Mastodon)