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.

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email