One-way street problem
Task number: 3962
Streets and intersections in a small town form a graph. We think of intersections as vertices and streets as edges. Prove that if the graph is two-connected, then all streets can be made one-way so that you can drive from every intersection to every other intersection without violating traffic regulations. (Such an orientation is called a strongly connected orientation.)
Decide whether the reverse implication also applies: ‘If the graph has a strongly connected orientation, then it is two-connected.’
Solution
By induction according to the number of ear. We orient each added ear in one direction. This is how we get the orientation we are looking for.
If \( u \) and \( v \) are selected vertices, then at least one of them is on the ear being added as otherwise the path exists by the induction hypothesis.
If both are on the added ear, then one of the paths, say from \( u \) to \( v \) corresponds to the orientation of the ear. We find the second path by moving from \( v \) in the direction of the arrows to the end of the ear, from it according to the inductive assumption we find an oriented path in the original graph to the beginning of the ear and then we complete the path to \( u \) .
If there is only one vertex, e.g \( u \) on the ear, then the searched paths can be similarly composed of two parts of the ear and suitable paths between \( v \) and the end of the ear \( x \) and \( y \). Specifically, if the ear is oriented \( x \to u \to y \), then we will find paths. \( v \to y \to v \) and \( v \to x \to u \).
The reverse implication does not holdy. We only get an edge two-connected graph. In fact, the assumption can be weakened and it can be proved that every two-connected graph has a strongly connected orientation, i.e. these two classes of graphs are identical.
We divide the given graph in articulations into two-connected blocks, on which we use the argument above. Then it is enough to show that the paths can be connected in articulations.
