Skip to interview prep
Apexed

217. What is the maximum number of edges in a simple graph with n vertices?

EasyGraph algorithms

Technical
Show model answer

A simple graph has no self-loops and no parallel edges. Undirected: each unordered pair of distinct vertices can be joined once, so n(n − 1)/2 edges (the complete graph K_n). Directed: each ordered pair can have an edge, so n(n − 1).

Allowing self-loops adds n more in each case. These bounds are why E = O(V²), so log E = O(log V), a fact used constantly in complexity analysis of graph algorithms.

What is the maximum number of edges in a simple graph with n vertices — Data structures & algorithms interview question — Apexed