A connected graph can have its edges assigned directions to make it strongly connected if and only if the graph has no bridge (no edge whose removal disconnects it). Proved by Herbert Robbins, it is a foundational orientability result of graph theory, originally motivated by a question about one-way street systems.
Facts
StatementThe graphs that have a strong orientation are exactly the 2-edge-connected graphs: an undirected graph G can be oriented into a directed graph with a path from every vertex to every other vertex if and only if G is connected and has no bridge. 2 Classification
Statement FormCharacterization Theorem 1 Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Sources
1. Wikipedia: Robbins' theorem
WikipediaLead section, statement-form referenceQuote, Lead section, statement-form reference
That is, it is possible to choose a direction for each edge of an undirected graph G, turning it into a directed graph that has a path from every vertex to every other vertex, if and only if G is connected and has no bridge.
2. Robbins' Theorem (Wikipedia)
Wikimedia FoundationLead section
states that the graphs that have strong orientations are exactly the 2-edge-connected graphs. That is, it is possible to choose a direction for each edge of an undirected graph G, turning it into a directed graph that has a path from every vertex to every other vertex, if and only if G is connected and has no bridge.
Lead section, proof year
Robbins' theorem, named after Herbert Robbins (1939), states that the graphs that have strong orientations are exactly the 2-edge-connected graphs.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.