Strongly Connected Directed Graphs
Definition
A directed graph is strongly connected if, for every ordered pair of distinct nodes , there exists a directed path from to and a directed path from to . Both directions must be possible for every pair.
This is stronger than ordinary connectivity: an undirected graph is connected if there is an undirected path between every pair, but a directed graph must have bidirectional reachability.
Condition for Orientability
An undirected graph can be oriented to become strongly connected if and only if every edge belongs to at least one cycle when considered in the undirected structure. The orientation must be consistent around each cycle: every edge in a cycle points the same direction around that cycle, ensuring that you can go from any node in the cycle to any other.
The 2025 Exam Question
The 2025 Q8f asked: given the A-H graph (A-B, A-E, B-C, B-F, C-D, C-F, D-F, D-H, F-G, G-H), can the undirected edges be given directionalities to make the resulting directed graph strongly connected?
Answer: No
The correct answer is no. The mark scheme states: “Nodes in the branch A-B-C can only be visited in one direction, so if one can go from A to C, one cannot go from C to A.”
Why Node E Makes It Impossible
Node E is a leaf: it has degree 1, connected only to A. If the edge A-E is directed A→E, then there is no path from E back to any other node (E has no outgoing edges). If directed E→A, then no path reaches E from any other node (E has no incoming edges from anywhere else). Either way, the strong connectivity condition fails for the pair (E, any other node).
Leaf nodes always prevent strong connectivity in directed graphs, unless the leaf has both an incoming and outgoing edge (which requires degree at least 2 in the underlying undirected graph).
The Mark Scheme Answer
1 mark: defining “strongly connected” correctly (every node reachable from every other). 1 mark: stating it is not possible. 1 mark: explaining why (the branch structure or the leaf node prevents bidirectional traversal).
General Rule
An undirected graph can be made strongly connected by assigning directions if and only if the graph is 2-edge-connected (no bridges). Every edge must be part of some cycle. If there is any bridge or leaf edge, its removal would disconnect the graph in one direction.
Summary
| Condition | Effect |
|---|---|
| Strongly connected | Directed path u→v and v→u for every pair |
| Graph has a leaf | Cannot be strongly connected |
| Every edge in a cycle | Orient consistency around each cycle → strongly connected |
| Bridge edge | Prevents strong connectivity |
| 2025 answer | Not possible (leaf E prevents bidirectional reachability) |
Past paper questions: y2025p3q8f