Why does a strongly connected directed graph with n vertices need at least n edges?
To ensure mutual reachability between every pair of vertices, the directed graph must contain at least one directed cycle that covers all n vertices. A directed cycle with n vertices has exactly n edges, which is the minimum required for strong connectivity.
Conditions
- G is a directed graph.
- G has n vertices.
- G is a strongly connected graph.
Reasoning, step by step
- Recognize that strong connectivity requires a path from u to v and v to u for all pairs.
- Deduce that the graph must contain a closed directed walk visiting all vertices.
- Construct a simple directed cycle connecting the n vertices sequentially.
- Count the edges in this cycle, which is exactly n.
- Conclude that n edges is the absolute minimum for a strongly connected directed graph.
Example
The instructor draws a directed cycle with 4 vertices (A, B, C, D) where A points to B, B to C, C to D, and D back to A. This uses exactly 4 edges (n) to achieve strong connectivity.
Common misconceptions
- Assuming that a directed graph can be strongly connected with n-1 edges, similar to an undirected connected graph.
- Confusing the minimum edge count for undirected connected graphs (n-1) with that for directed strongly connected graphs (n).
Watch the explanation
7:06 – 7:24Watch this moment ↗
Explore next
Answers are generated from source material and independently checked. Consult the original video or creator if something is unclear.