Robbins' theorem

Robbins' theorem states that a finite connected undirected graph can be oriented to become strongly connected if and only if it has no bridges.

Connect

Strong orientation: An orientation of an undirected graph that produces a strongly connected directed graph. This is the orientation whose existence Robbins' theorem characterizes.
Graph connectivity: The study of whether vertices remain connected after edges or vertices are removed from a graph. Robbins' theorem is a precise criterion about connectivity under edge orientation.
Herbert Robbins: An American mathematician known for work in graph theory, statistics, and mathematical optimization. Robbins proved the orientation criterion that bears his name.
One-way street: A road on which motor traffic is permitted to travel in only one direction. Road networks illustrate the theorem’s question of directing links without isolating regions.
Acyclic orientation: An orientation of an undirected graph that contains no directed cycle. A nontrivial strongly connected orientation contains directed cycles, unlike an acyclic orientation.
Depth-first search: A graph traversal that explores each vertex's unvisited neighbors recursively, producing a rooted tree. A depth-first search tree supports a direct construction of the required orientation.
Connected graph: An undirected graph in which every pair of vertices is joined by a path. Connectedness is the theorem’s starting condition before edges receive directions.
One-way street problem: The problem of directing the edges of a connected graph so that every vertex can reach every other. This practical formulation motivated the search for a bridge-based criterion.
Communication network: A system of nodes connected by channels that carry information between them. An orientation models one-directional channels, while strong connectivity ensures mutual reachability.
Eulerian orientation: An orientation of a graph in which each vertex has equal indegree and outdegree. Eulerian balance is a different orientation property from strong connectivity.