2015 Danube Mathematical Competition

Given any orientation, the total number of edges equals the sum of all out-degrees. If the latter are all even, then so is the former.

To establish the converse, induct on the number of edges to show that any connected simple finite graph with an even number of edges splits into edge-disjoint paths of length $2$. Orient the two edges of each of these paths away from the joint to obtain the required orientation.

Alternative Solution.

The problem is a special case of the following general fact: Given a connected finite simple graph $G=(V,E)$ and an integral-valued function $f$ on $V$, taken over all possible orientations of the edges of $G$, the minimum of the number of vertices at which outdeg and $f$ have opposite parities is $|E|-{\sum }_{x\in V}f(x)$ reduced modulo $2$.

Given any orientation, notice that the number of vertices at which the parities of outdeg and $f$ disagree has the same parity as $|E|-{\sum }_{x\in V}f(x)$. Consider an orientation minimising the number of these vertices. If this number exceeds $1$, choose two such vertices and use connectedness to join them by a path. Reverting orientations along the path changes the parity of out-degrees only at the end-points, so the outcome is an oriented graph with fewer vertices at which outdeg and $f$ have opposite parities. This contradicts minimality and concludes the proof.