---
tag: 03WKB2H474
kind: example
name: Complete graph
msc: [05C99]
instance_of: [00C0BR7D7H]
sources:
  - url: https://en.wikipedia.org/wiki/Complete_graph
    locator: lead section
same_as:
  wikidata: Q45715
  wikipedia: Complete graph
---

## Example

Let $n$ be a natural number.
The complete graph $K_n$ is the [[graph|0JD5C82QMB]] with vertex set $\{1, \dots, n\}$ in which any two distinct vertices are adjacent.

More generally, the complete graph on a set $V$ has an edge between each pair of distinct elements of $V$.

## Remarks

The graph $K_n$ is $(n-1)$-[[regular|0KA4S8R39M]], and it has $\binom{n}{2}$ edges. The node [[number of edges of a complete graph|05RN90E14Y]] states this.
$K_3$ is a triangle. $K_4$ is planar, and [[$K_5$ is not planar|030A3FHN14]].
A clique in a graph is a set of vertices that induces a complete graph.

## Explanations

### L1 human

In a complete graph every vertex is joined to every other vertex.
If $5$ people all shake hands with each other, the handshakes form $K_5$.