Complete Graph Edges

In one sentence: A complete graph joins every pair of points with one line, and this formula counts how many lines that takes, given how many points there are.

$E = \frac{n(n-1)}{2}$

Read it out loud: “E equals n times the quantity n minus 1, divided by 2. E is the number of edges, the lines that join the points. n is the number of vertices, the points. Work out the top part first: multiply n by n minus 1, then divide the answer by 2.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Graph, vertex and edge: In mathematics a graph is a set of vertices, which are points or dots, joined by edges, which are lines. A graph records only which points are joined, not where they are drawn or how long the lines are. A network of computers is a graph: each computer is a vertex, and each cable between two computers is an edge.
Pairs of points: A pair is two different points taken together. With three points A, B and C, the pairs are AB, AC and BC, which makes 3 pairs. Each edge joins exactly one pair, so counting edges is the same as counting pairs. The pair AB and the pair BA are the same pair, because a line does not care which end you start from.
Subscripts and the name $K_n$: The name $K_n$ is read ‘K sub n’. The letter $K$ is a common label for a complete graph, and the subscript $n$ says how many vertices it has. So $K_{5}$ is the complete graph on 5 vertices. A subscript is a name, not a multiplication, so $K_n$ is one single graph.
Brackets and the fraction bar: Work inside brackets comes first. A fraction bar works like brackets: everything above the bar is worked out before the division below it. So in $\frac{n(n-1)}{2}$ , the top $n(n-1)$ means $n \times (n - 1)$ , which is found first, and then the whole top is divided by 2.
Choosing 2 of $n$ items: The number of pairs is the number of ways to choose 2 items from $n$ items when the order does not matter. It is written $\binom{n}{2}$ , read ‘n choose 2’, and it equals $\frac{n(n-1)}{2}$ . For example, with 4 items, $\binom{4}{2} = \frac{4 \times 3}{2} = 6$ pairs.

What each symbol means

Symbol	Meaning
$E$	The number of edges: the lines that join pairs of vertices. In a complete graph each pair of vertices has exactly one edge between them. It is a plain count with no unit. The party example below has 45 edges.
$n$	The number of vertices, the points or nodes of the graph. It is a whole number of at least 1, with no unit. A complete graph with $n$ vertices is written $K_n$ . The party example uses $n = 10$ , one vertex for each person.

The formula piece by piece

$n - 1$: How many other vertices one vertex can join. A vertex is not joined to itself, so it links to the other $n - 1$ vertices. With 10 vertices, each one has $10 - 1 = 9$ edges leaving it.
$n(n - 1)$: The edges counted from every vertex. There are $n$ vertices, and each has $n - 1$ edges leaving it, so the total is $n(n - 1)$ . With 10 vertices it is $10 \times 9 = 90$ . This is too big, because each edge was counted once from each of its two ends.
$\frac{n(n-1)}{2}$: Divide by 2 to remove the double count. Each edge was counted from both of its ends, so the true number of edges is half of $n(n-1)$ . With 10 vertices it is $90 \div 2 = 45$ edges.
$E = \frac{n(n-1)}{2}$: The whole formula as one sentence: the number of edges in a complete graph equals the number of vertices times one less than that number, divided by 2. Each vertex joins every other vertex, and each edge is counted once.
$E = \binom{n}{2}$: The same count written as ‘n choose 2’, the number of ways to pick 2 of the $n$ vertices when the order does not matter. Each pair of vertices gives one edge, so this is the same number as $\frac{n(n-1)}{2}$ .

What the formula is doing, and why

A graph is a set of vertices joined by edges. In a complete graph, every pair of different vertices is joined by exactly one edge. There are no missing links and no doubled links. The complete graph with $n$ vertices is written $K_n$ .

Why multiply, then divide? Each vertex has $n - 1$ edges leaving it, because it joins every other vertex. Over all $n$ vertices, that gives $n(n - 1)$ . But every edge was counted twice, once from each of its two ends. So the true count is half of that, which gives $E = \frac{n(n-1)}{2}$ .

The handshake form. Think of $n$ people who each shake hands once with everyone else. Each handshake is one edge, joining two people. If Ana shakes hands with Ben, that is one handshake, and it is the same handshake as Ben shaking hands with Ana. This is why the count is halved, and the formula gives the same number of handshakes as edges.

Why it grows quickly. Because $n(n - 1)$ is close to $n^{2}$ when $n$ is large, doubling the number of vertices roughly quadruples the number of edges. That is why a full network of many machines needs far more links than a tree or a ring. The count is always close to half of $n^{2}$ for a large $n$ .

When does it apply? Only when every pair of vertices is joined. If some pairs have no edge, the graph is not complete, and it has fewer edges than the formula gives.

An everyday picture

Think of a group chat with five people in which every pair of people also has a private chat with each other. Each person has four private chats, one with each of the other four people. Each private chat is shared by two people, so the number of private chats is $\frac{5 \times 4}{2} = 10$ . The people are the vertices, and the private chats are the edges.

Worked example: Handshakes at a party of 10 people

At a party, 10 people each shake hands once with every other person. Nobody shakes hands with themselves. So there are $n = 10$ vertices, one for each person, and each handshake is one edge that joins two people. The party is made up for this example, to show how the formula counts.

Write down the input. The number of people is $n = 10$ , so the graph has 10 vertices. Each pair of people shakes hands exactly once, so every pair of vertices has one edge between them. We want the number of handshakes, which is the number of edges.
Count the handshakes for one person. One person shakes hands with everyone except themselves. That is $n - 1 = 10 - 1 = 9$ handshakes for each person.
Count the handshake ends for everyone. Over all 10 people, the count is $10 \times 9 = 90$ . But each handshake involves two people, so it was counted twice, once for each person in it. The next step removes the double count.
Divide by 2 to count each handshake once. $90 \div 2 = 45$ handshakes. Dividing by 2 removes the double count, because each handshake has exactly two people, and each one was counted once for each of them.
Check with the formula. $E = \frac{n(n-1)}{2} = \frac{10 \times 9}{2}$ . Work out the top first: $10 \times 9 = 90$ . Then divide: $90 \div 2 = 45$ . The formula and the step-by-step count give the same answer.
Add an eleventh person. With $n = 11$ , the formula gives $\frac{11 \times 10}{2} = 55$ handshakes. The new person adds $55 - 45 = 10$ handshakes, one with each of the 10 people who were already at the party.
See how fast the count grows. With 20 people the count is $\frac{20 \times 19}{2} = 190$ handshakes. Doubling the people, from 10 to 20, makes $190 \div 45 \approx 4.2$ times as many handshakes, which is more than four times.

Answer: The 10 people shake hands 45 times. With 11 people the count rises to 55, so the new person adds 10 handshakes. With 20 people there are 190 handshakes, which is more than four times the count for 10 people.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Forgetting to divide by 2. Counting from each vertex counts every edge twice, once from each of its ends, so the answer is double the true number.
Using $n$ instead of $n - 1$ for the edges at one vertex. A vertex is not joined to itself, so it has $n - 1$ edges, not $n$ .
Using the formula for a graph that is not complete. If some pairs are not joined, the graph has fewer edges than the formula gives.
Thinking the count is $n^{2}$ . The true count is about half of $n^{2}$ , because each edge joins two vertices and is counted only once.

Where you will meet it

Sizing a full-mesh network, where every device has a direct link to every other device.
Solving handshake problems, where each pair of people shakes hands once.
Round-robin tournaments, where each pair of teams plays exactly one game.
Graph theory, where complete graphs are the standard examples of graphs with the most possible edges for their number of vertices.

Questions people ask

Is a complete graph the same as a cycle?

No. In a cycle each vertex has 2 edges, joining the vertices in a loop. In a complete graph each vertex has $n - 1$ edges, because every pair is joined. Five vertices make a cycle with 5 edges, but a complete graph on five vertices has $\frac{5 \times 4}{2} = 10$ edges.

Does direction matter in this formula?

Not here. The formula counts undirected edges, where each edge joins two vertices with no direction. A directed graph uses arrows instead, and a directed version with an arrow in both directions for every pair has $n(n - 1)$ arrows.

How many edges does a graph with one vertex have?

Zero. A single vertex has no other vertex to connect to, and $\frac{1 \times 0}{2} = 0$ .

Euler's Formula for Planar Graphs: Euler’s formula says that if you draw a connected network on a flat sheet with no crossing lines, then corners minus lines plus regions always comes to 2.
PageRank: PageRank gives each web page a score based on which other pages link to it, and a link from a page with a high score counts for more.
Perfect Binary Tree Nodes: The formula counts every node in a perfect binary tree, a branching diagram in which each row is completely full, using only the number of rows below the top.