Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams

We initiate the study of k-edge-connected orientations of undirected graphs through edge flips for k ≥ 2. We prove that in every orientation of an undirected 2k-edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge connectivity, and the final orientation is k-edge connected. This yields an "edge-flip based"new proof of Nash-Williams' theorem: A undirected graph G has a k-edge-connected orientation if and only if G is 2k-edge connected. As another consequence of the theorem, we prove that the edge-flip graph of k-edge-connected orientations of an undirected graph G is connected if G is (2k+2)-edge connected. This has been known to be true only when k=1.