# 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