Nash-Williams' strong orientation theorem
From Egres Open
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].
References
- ↑ 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
- ↑ H. N. Gabow, Efficient splitting off algorithms for graphs, DOI link
