Per Wikipedia:
In graph theory, a strong orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that makes it into a strongly connected graph.
A natural question that follows: which undirected graphs have a strong orientation?
Robbins’ theorem
Robbins’ theorem states that the set of graphs with strong orientations is precisely the set of bridgeless graphs.
Lemma. This condition is necessary (i.e. any graph with a bridge cannot have a strong orientation).
Proof. This picture should make the argument clear:
If the edge is directed from , then no node in can reach any node in . Symmetric for .
We now prove the more difficult half of the theorem:
Lemma. This condition is sufficient (i.e. any bridgeless graph has a strong orientation).
Proof. Robbins’ original proof of his theorem introduces a tool called ear decomposition : for more on that, you can check out this Codeforces blog.
Today, I’ll present another approach which Wikipedia cites as Boesch and Tindell’s. The core claim is as follows:
Consider a mixed graph (i.e. with both directed and undirected edges) such that every pair of nodes in can reach one another. If there exists an undirected edge in that is not a bridge, we always assign a direction to this edge such that all-pairs connectivity is preserved.
If this is true, we can direct all the edges of a bridgeless graph in any order until the entire graph is an SCC.
Two examples of such mixed graphs, and the corresponding orientation (shown in blue) assigned to the edge .
Proof of claim. Consider the graph (i.e. with edge removed). We wish to show that in this graph, there always exists a path either from or from . If the former is true, we can direct this edge from ; otherwise, we can direct this edge from .
Our all-pairs connectivity condition means that all nodes must be reachable from . This means that in , all nodes must be reachable from either or . By a similar line of reasoning, all nodes in must be able to reach either or as well.
Therefore, all nodes fall under four categories:
- (reachable from , can reach )
- (reachable from , can reach )
The four categories of nodes. Note that one node could potentially fall under multiple categories.
Observe that if any nodes of type or exist, our claim is clearly true. Otherwise, all nodes are of either type or type , but then would be a bridge which contradicts our assumption. Thus, we have proved the desired claim.
If only type 1 and type 4 nodes exist, the graph looks something like this. The red edge cannot exist in either direction because then a type 2/3 node would exist, which contradicts our assumption.