Nash-Williams' edge-connectivity orientation conjecture

For a natural number kk, a graph is 2k2k-edge-connected if every edge cut has size at least 2k2k, and an orientation is kk-arc-connected if every ordered pair of vertices is joined by at least kk edge-disjoint directed paths. Nash-Williams' edge-connectivity orientation conjecture. For any natural number kk, every 2k2k-edge-connected graph admits a kk-arc-connected orientation. This is the edge-connectivity consequence of Nash-Williams' orientation problem for arbitrary graphs. The supplied status evidence says that this problem was answered by Thomas, who proved that one can take f(k)=8kf(k)=8k; accordingly, this candidate is recorded as solved.

Sources & referencesView supporting material

Primary source

Leandro Aurichi, Paulo Magalhães Júnior and Guilherme Eduardo Pinto, “On orientations preserving edge-connectivity in infinite graphs”, arXiv:2510.06449 (2025).

Additional references

2 papers in this index state this conjecture (2023–2025). The statement above is taken from the most recent of them; the others are arXiv:2306.10631.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.