---
tag: 05RN90E14Y
kind: statement
role: proposition
name: Number of edges of a complete graph
msc: [05C30]
uses: [092GEF38YD, 03WKB2H474]
sources:
  - url: https://en.wikipedia.org/wiki/Complete_graph
    locator: Properties
---

## Statement

Let $n$ be a natural number.
Then the [[complete graph|03WKB2H474]] $K_n$ has exactly
$$\binom{n}{2} = \frac{n (n - 1)}{2}$$
edges.

## Remarks

The edges of $K_n$ are exactly the $2$-element subsets of the vertex set. The [[number of k-element subsets|0BFMR2FQ8B]] gives the count.
The [[handshaking lemma|0XAP8WHNES]] gives the same count: $n (n - 1) = 2 |E|$.
Each simple graph on $n$ vertices has at most $\binom{n}{2}$ edges.

## Explanations

### L1 human

If $n$ people all shake hands with each other, there are $\frac{n(n-1)}{2}$ handshakes.
Each person shakes $n - 1$ hands, and this counts each handshake twice.