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.[ref]
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)
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.[ref]
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
Articles by others on the same topic
Robbins' theorem is a significant result in the field of Boolean algebra and combinatorial logic, primarily related to the minimization of Boolean functions. The theorem, formulated by Howard Robbins in 1937, states that any boolean function can be represented using a certain set of logical operations. Specifically, it provides a characterization of boolean functions that can be expressed using certain combinations of the logical operations AND, OR, and NOT.