= Robbins' theorem
{c}
{wiki}
A finite nonempty <connected graph> whose <edges> are undirected admits a <strong orientation> if and only if it has no <bridge in a graph>. This statement holds for finite <multigraphs> as well as finite <simple graphs>; <self-loops> do not help connect distinct <vertices>. The single-<vertex> case is allowed, with length-zero <directed paths>.<On Orientations and Shortest Paths by Refael Hassin and others>[Hassin and Megiddo, On Orientations and Shortest Paths (1989), printed pp. 591–592: bridge-connectedness, strong connectivity and Theorem 2.6 (Robbins)]{ref}
Necessity comes from the two sides separated by deleting a <bridge in a graph>: its chosen arrow crosses in only one direction. For sufficiency, the cited constructive proof uses <depth-first search> to find a <cycle in a graph>, orients it cyclically, contracts it, and repeats. Undoing the contractions replaces junctions by <directed cycles>, retaining two-way <reachability>. Contraction can produce <multiple edges>, so these must remain distinct. This is a construction outline; the input <graph> is finite and bridgeless, and remaining <edges> within contracted pieces can receive arbitrary directions.<On Orientations and Shortest Paths by Refael Hassin and others>[Hassin and Megiddo (1989), Theorem 2.6 proof, printed p. 592: cycle orientation and contraction, explicitly described as a different constructive proof from Robbins's]{ref}
Back to article page
