Edges in a complete graph
Count edges joining every pair of distinct vertices.
Edges in a complete graph is one of 4 graphs formulas in the discrete math section of this library, and it is used at high school · university level.
Why edges in a complete graph works
Each of the n vertices reaches out to the other n − 1, which suggests n(n − 1) connections. But that counts every edge twice, once from each endpoint, so halving it gives the true total. The same count is what the binomial coefficient n choose 2 means: the number of ways to pick an unordered pair.
What each symbol means
$K_n$ is the simple complete graph on $n$ vertices.
Edges in a complete graph: when it holds
No loops or parallel edges are included.
When it stops applying
It counts simple graphs only, with no loops and no repeated edges. A directed complete graph has an arrow each way, so it holds n(n − 1) arcs, which is 20 for five vertices rather than 10.
Edges in a complete graph: a worked example
$K_5$ has $5(4)/2=10$ edges.
The mistake to avoid
What people do: Students report n(n − 1) and skip the division by two.
Why it goes wrong: That counts the edge from A to B and the edge from B to A as different things, when in an undirected graph they are the same single edge.
Do this instead: Divide by 2 at the end. K₅ has 5(4)/2 = 10 edges, and you can confirm it by drawing the pentagon with its five diagonals.
Edges in a complete graph: step by step
- Name the unknown, and the unit the answer has to come out in.
- Match the symbols to your values. $K_n$ is the simple complete graph on $n$ vertices.
- Check the conditions before substituting. No loops or parallel edges are included.
- Substitute, keep exact values to the last line, then test the sign, size, and unit against a rough estimate — the check that catches most discrete math slips.
Where this formula fits
- Subject
- Discrete Math formulas — 11 entries in this library
- Topic
- Graphs
- Level
- High school · University
Formulas are easiest to keep when they sit inside a method rather than on a list. Use the links below to see where edges in a complete graph comes from, to check a calculation against a tool, and to practise it until you can recall it without looking.
- Discrete Math Calculator — check your substitution and the value it produces.
- Study discrete math — the subject guide that explains the ideas these formulas compress.
- Discrete Math Practice — questions that make you retrieve the formula instead of recognising it.
- All 11 discrete math formulas — the full grouped reference, or the complete formula library.
Questions about edges in a complete graph
If ten people all shake hands once, how many handshakes happen?
Forty-five, from 10(9)/2. The number climbs fast, which is why meetings where everyone must talk to everyone become impossible well before the room is full.
How do I work backwards from the edge count to n?
Solve n(n − 1)/2 for the count. Twenty-one edges gives n(n − 1) = 42, and since 7 times 6 is 42, the graph has 7 vertices.
What does the notation n choose 2 mean here?
It counts how many ways you can pick 2 items from n without caring about order, and each such pair is exactly one edge. That is why the graph count and the combinations count are the same number.
Why is a complete graph the worst case for algorithms?
Because its edge count grows with the square of the vertex count. Doubling the vertices roughly quadruples the edges, so anything that visits every edge slows down four times over.