Nash-Williams' strong orientation theorem

From Egres Open
Jump to: navigation, search

Theorem (Nash-Williams [1]). Every undirected graph has a well-balanced orientation.

The proof of Nash-Williams contains a slightly stronger result: every undirected graph has a feasible odd vertex pairing. A well-balanced orientation of G can be obtained by adding a feasible odd vertex pairing to G, and taking an arbitrary Eulerian orientation of the resulting graph. An efficient algorithm for finding a feasible odd vertex pairing is described by Gabow [2].


  1. C. St. J. A. Nash-Williams, On orientations, connectivity and odd vertex pairings in finite graphs, Canad. J. Math. 12 (1960) 555-567, journal link
  2. H. N. Gabow, Efficient splitting off algorithms for graphs, DOI link