Orientation conjecture of Nash-Williams

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $k\in\mathbb N$, and let $G$ be an undirected multigraph, possibly infinite, with parallel edges allowed. Loops do not affect any connectivity below. Say that $G$ is $q$-edge-connected when each edge cut separating two vertices has size at least $q$; equivalently any two vertices admit $q$ pairwise edge-disjoint finite paths. An orientation assigns a direction to every nonloop edge. A digraph is $k$-arc-connected when for each ordered pair $(u,v)$ of distinct vertices there are $k$ pairwise arc-disjoint finite directed paths from $u$ to $v$, equivalently every nontrivial directed outgoing cut has at least $k$ arcs.

Statement recorded in the supplied source.

Does every $2k$-edge-connected undirected multigraph, including arbitrary infinite graphs, have a $k$-arc-connected orientation? No local-finiteness or restriction on the number of ends is imposed. [S2]

Short English statement

Does twice the undirected edge connectivity always guarantee a directed orientation with the required connectivity, even in infinite multigraphs?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3000059 (AMR-029-0059). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 A. Assem, M. Koloschin and M. Pitz, The Nash-Williams orientation theorem for graphs with countably many ends (2024), Introduction, Conjecture 1.2 and graph-connectivity definitions, pp.1--2. https://arxiv.org/pdf/2310.03601.