0,1 graph orientation

(Samuel challenges me): Let $G$ a graph and $D$ an orientation of $G$, i.e. a choice of direction for the edges of $G$. Define $\delta (v) = \mid d_\text{in}(v) - d_\text{out}(v) \mid$, show that for every graph $G$ there exists an orientation $D$ such that for every vertex $v$, $\delta(v) \in \{0,1\}$.
Solution:

First, this is immediate for paths or cycles: In paths only the end vertices are $\delta(v)=1$ and the others $\delta(v) = 0$, for cycles all vertices are $\delta(v)=0$.
For trees, it is easy to observe inductively that roots and leaves are $\delta(v) = 1$ and intermediate vertices are $\delta(v)=0$.

Eulerian circuits are nice: If $G$ admits an Eulerian circuit, then orient it according to the Eulerian circuit and all vertices will be $\delta(v)=0$.
But what if the graph does not admit an Eulerian circuit ? Let’s show two well know results.

(Lemma 1): The number of vertices of odd degree is even, in any graph.
Proof: By the handshaking lemma $\sum_{v \in V} d(v) = 2m$.
Since $2m \equiv 0 (\text{mod }2)$, then
$\sum_{v \in V} d(v) =$
$\sum_{v \in V \land d(v) \equiv 0(\text{mod }2)}d(v) + \sum_{v \in V \land d(v) \equiv 1(\text{mod }2)} d(v) \equiv$
$0 (\text{mod }2) \Rightarrow$
$0 + \sum_{v \in V \land d(v) \equiv 1(\text{mod }2)} d(v) \equiv 0 (\text{mod }2)$.
The number of vertices of odd degree is congruent to zero modulo 2, i.e. even. QED

(Lemma 2): If the degree of every vertex is even in $G$, then $G$ admits an Eulerian circuit.
Assume that every vertex in the connected graph $G$ has even degree. By induction in $m$, if $m=0$, this is an Eulerian circuit.
The inductive hypothesis is to assume that any connected graph with $0,1,…,k$ edges where every vertex has an even degree contains an Eulerian circuit.
Let $G$ be a connected graph with $k+1$ edges where every vertex has an even degree. Since every vertex $v \in V(G)$ has $d(v) \geq 2$ and $G$ is connected, $G$ is not a tree, thus $G$ must contain at least one simple cycle $C$.
Let $H$ be a graph such that $V(H) = V(G)$ and $E(H) = E(G) \backslash E(C)$. By construction, if $v \in C \subset G$ then $d_H(v) = d_G(v) - 2$, if not, $d_H(v) = d_G(v)$. $H$ may consist of disconnected components. By the induction hypothesis, each component has a Eulerian circuit, with $C$, this consists an Eulerian circuit of $G$. QED

Now, let’s prove the statment. I did this proof on the blackboard together with Heitor a while ago.

If $G$ is an Eulerian circuit, then the proof is done.
If $G$ is not an Eulerian circuit, we know there are at least two vertices of odd degree, as proven in Lemma 1 and Lemma 2 (there may be more).
Let $K$ a graph such that $V(K) = V(G) \cup \{u\}$ and $u \notin V(G)$, and $E(K) = E(G) \cup \{u v | v \in V(G)$ and $d(v)$ is odd$\}$.
In $K$, all vertices from $G$ has even degree by construction, also $u$ by Lemma 1. Thus, by Lemma 2, this is an Eulerian circuit, choose this orientation, and for every vertex of $K$, $\delta(v) = 0$. Upon removing $u$ and its edges, the vertices that had an odd degree in $G$ become $\delta(v) = 1$ in $G$, and the even ones remain $\delta(v)=0$. QED