The maximum number of edges in a graph depends on the rules of the graph. The most common version of the question assumes a simple graph, which means no self-loops and no duplicate edges. Under that assumption, the answer is determined entirely by the number of vertices.

Start with the Assumptions

Before using any formula, check what kind of graph you have:

• A simple undirected graph has no self-loops and no multiple edges.
• A simple directed graph has no self-loops, but direction matters.
• If parallel edges are allowed, there may be no finite maximum at all.

That last point is important. If you can keep adding another edge between the same two vertices, then "maximum number of edges" stops having a useful finite answer.

Undirected Simple Graphs

In an undirected simple graph with n vertices, each edge connects one unordered pair of distinct vertices. So the maximum number of edges is the number of ways to choose 2 vertices from n.

That gives the formula:

n * (n - 1) / 2

This maximum is achieved by the complete graph K_n, where every vertex is connected to every other vertex.

For example, if n = 5, the maximum is:

5 * 4 / 2 = 10

So a simple undirected graph with 5 vertices can have at most 10 edges.

Directed Simple Graphs

For a directed graph, the edge from u to v is different from the edge from v to u. That means each ordered pair of distinct vertices can contribute one edge.

The maximum becomes:

n * (n - 1)

For n = 5, that gives:

5 * 4 = 20

So the directed maximum is twice the undirected maximum for the same number of vertices.

Why the Formula Works

The reasoning is straightforward:

• Undirected case: count unordered pairs of vertices.
• Directed case: count ordered pairs of vertices.

You do not need to inspect a particular graph instance. Once the graph type and the number of vertices are fixed, the maximum follows directly from counting.

Here is a small Python snippet that computes both values:

1def max_undirected_edges(n: int) -> int:
2    if n < 0:
3        raise ValueError("n must be non-negative")
4    return n * (n - 1) // 2
5
6
7def max_directed_edges(n: int) -> int:
8    if n < 0:
9        raise ValueError("n must be non-negative")
10    return n * (n - 1)
11
12
13for n in [0, 1, 2, 5]:
14    print(
15        f"n={n}",
16        f"undirected={max_undirected_edges(n)}",
17        f"directed={max_directed_edges(n)}",
18    )

Expected output:

1n=0 undirected=0 directed=0
2n=1 undirected=0 directed=0
3n=2 undirected=1 directed=2
4n=5 undirected=10 directed=20

Dense Versus Sparse Graphs

This maximum is also the reference point for graph density.

For many graph algorithms, the choice of representation depends heavily on whether the graph is sparse or dense. That makes the maximum-edge formula more than just a theoretical result.

Common Pitfalls

• Forgetting the word "simple". The formula changes if loops or duplicate edges are allowed.
• Using n^2 for an undirected graph. That overcounts because (u, v) and (v, u) are the same edge.
• Forgetting that self-loops are excluded in a simple graph.
• Mixing up directed and undirected formulas.

Summary

• In a simple undirected graph, the maximum number of edges is n * (n - 1) / 2.
• In a simple directed graph without self-loops, the maximum number of edges is n * (n - 1).
• The maximum is achieved by a complete graph.
• Dense and sparse graphs are defined relative to this maximum.
• Always confirm the graph assumptions before applying the formula.