Balanced orientation of infinite graphs

Question

all I am asked to prove that given a loopless multigraph $G$ with vertices all having even degree, it is possible to orient the graph in such way that the in-degree of every vertex is equal to the out degree of every vertex. Now for the case when the number of vertices finite, this is easy using Eulerian trails. However, I am curious if the same statement holds for a graph having countably infinite vertices all with even degree and finitely many edges? Any help in see why or why the infinite graph case is true would be awesome.

Answer 1

Well, for any finite set of vertices $S$ in the infinite graph, we can orient the edges incident to those vertices so that in-degree equals out-degree.

(This can be proven from the finite case, but is not entirely trivial: to apply the proof for finite graphs, we should create a finite graph on vertex set $S \cup \{v^*\}$, where each edge $vw$ with $v \in S$, $w\notin S$ is replaced by an edge $vv^*$.)

We can go from there to the infinite case by a similar argument as the proof of the de Bruijn–Erdős theorem. Let $X = \{\gets, \to \}^{E(G)}$ be the set of all orientations of the edges, which we make a topological space by giving it the product topology (of the discrete 2-element spaces for each edge). For each set $S \subseteq V(G)$, let $X_S$ be the set of all orientations such that vertices in $S$ have equal in-degree and out-degree. Each $X_S$ is closed: it is a finite union of sets of orientations defined by specifying what they do on edges incident to $S$.

By Tychonoff's theorem, $X$ is compact, and the sets $X_S$ have the finite intersection property, so the intersection $\bigcap_{S \subseteq V(G)} X_S$ is nonempty; any element of that intersection is a balanced orientation of $G$.

The other option is to say "by the standard compactness argument, the same holds for infinite graphs" and hope nobody asks you what the standard compactness argument is. (It's the thing above.)

Answer 2

In what follows a graph is a loopless multigraph, not necessarily finite. A graph $G$ is empty if it has no edges, locally finite if each vertex has finite degree. The axiom of choice will be used.

Lemma. If $G$ is a nonempty graph with no vertices of degree one, then $G$ has a $2$-regular subgraph.

Proof. Obvious.

Theorem. If $G$ is a locally finite graph with all vertices having even degree, then there is a family $G_i$ $(i\in I)$ of edge-disjoint $2$-regular graphs such that $E(G)=\bigcup_{i\in I}E(G_i)$.

Proof. Let $\{G_i:i\in I\}$ be a maximal collection of edge-disjoint $2$-regular subgraphs of $G$. By the lemma, $E(G)\setminus\bigcup_{i\in I}E(G_i)$ must be empty.

Corollary. If $G$ is a locally finite graph with all vertices having even degree, then $G$ has a balanced orientation.

Proof. Take a family $\{G_i:i\in I\}$ as in the theorem, and choose a balanced orientation for each $G_i$.

P.S. A more general statement.

Recall that a graph is a loopless multigraph, not necessarily finite or locally finite.

Lemma. If $G$ is a nonempty graph, then $G$ has a connected subgraph $H$ such that, for each vertex $v$ of $H$, $\deg_H(v)$ is either one or two; moreover, $\deg_H(v)=1$ only if $\deg_G(v)=1$.

Proof. Obvious.

Theorem. Any graph $G$ has an orientation in which the indegree and outdegree of any vertex differ by at most one. (In particular, for any vertex whose degree is infinite or even, the indegree and outdegree are e4qual.)

Proof. We define edge-disjoint subgraphs $H_\alpha$ of $G$ by transfinite recursion. Let $\alpha$ be an ordinal and suppose $H_\beta$ has already been defined for all $\beta\lt\alpha$. Let $G_\alpha$ be the graph obtained from $G$ by deleting the edges of the graphs $G_\beta$, $\beta\lt\alpha$. If $E(G_\alpha)=\emptyset$, we stop; otherwise, applying the lemma to $G_\alpha$, we get a connected subgraph $H_\alpha$ of $G_\alpha$ such that each vertex $v$ of $H_\alpha$ has degree one or two in $H_\alpha$, with $\deg_{H_\alpha}(v)=1$ only if $\deg_{G_\alpha}(v)=1.$

Now $G$ is the union of the edge-disjoint subgraphs $H_\alpha$, and each vertex $v$ of $G$ has degree $2$ is each $H_\alpha$ that contains it with at most one exception. Choose for each $H_\alpha$ an orientation in which each vertex of degree two has indegree and outdegree equal to one. Take the union of hese orientations to get our orientation of $G$. In particular, each vertex whose degree is infinite or finite and even has outdegree equal to its indegree.