Why is the maximum number of edges in a directed graph with n vertices $n(n-1)$?

Conditions

• G is a directed graph.
• G has n vertices.
• We are seeking the maximum possible number of edges.

Reasoning, step by step

1. Recall that an undirected complete graph with n vertices has $n(n-1)/2$ edges.
2. Recognize that in a directed graph, each unordered pair of vertices can support two directed edges (one in each direction).
3. Multiply the undirected maximum by 2: $2 * [n(n-1)/2]$.
4. Simplify to get the directed maximum: $n(n-1)$.

Example

The instructor explains that because a directed graph has two edges between a pair of vertices—one pointing forward and one pointing backward—we multiply the undirected base count by two, resulting in $n(n-1)$.

Common misconceptions

• Mistakenly equating the maximum number of edges in a directed graph with that in an undirected graph ($n(n-1)/2$).
• Assuming that self-loops (edges from a vertex to itself) are included in this standard maximum count.

Watch the explanation

Explore next

• Why does an undirected graph with n vertices have at most $n(n-1)/2$ edges?
• Why does a strongly connected directed graph with n vertices need at least n edges?
• What is the maximum number of edges in a disconnected undirected graph?