Nash-Wiliams theorem

Task number: 4250

Show that the edges of each planar graph can be oriented so that each vertex has an outdegree at most 3.

  • Hint

    Choose any orientation and incrementally reduce the outdegrees of the selected vertices by switching the orientation along cleverly selected paths.

  • Solution

    Suppose that in some orientation of a given graph \( G \) the vertex \( u \) has an outdegree at least four.

    Let us denote by \( S \) the set of vertices to which exist an oriented path from \( u \). It holds that the subgraph \( G [S] \) of the graph \( G \) induced by the set \( S \) is also a subgraph \( G \) induced by the edges that emanate from the vertices \( S \). Because \( G \) is planar, \( G [S] \) is also planar. It follows from Euler’s formula that \( G [S] \) can have at most \( 3 | S | -6 \) edges. Therefore, in \( G [S] \) necessarily lies the vertex \( v \), whose outdegree is at most 2 – if such a vertex does not exist, \( G [S] \) would have at least \( 3 | S | \) edges.

    By switching the edges on the path from \( u \) to \( v \), we obtain a graph in which the outdegree of \( u \) is reduced, and the outdegree of \( v \) does not exceeded three. The outputdegrees of the other vertices remain unchanged.

    By repeating the above procedure, we eliminate all vertices whose outdegree is at least four.

Difficulty level: Hard task
Proving or derivation task
Solution require uncommon idea
Cs translation
Send comment on task by email