Balanced orientation
Task number: 4456
Consider an undirected graph whose vertices all have even degrees. Prove that it is possible to orient the edges so that at each vertex the input degree is equal to the output degree.
Solution
Without loss of generality, the graph is connected (otherwise we process each component separately).
By the theorem on the characterization of Eulerian trails in a connected graph with even degrees, there exists a closed Eulerian trail. It is sufficient to traverse the trail in one of the possible directions and orient the edges along the trail.
