Complete graph

Example

Let $n$ be a natural number. The complete graph $K_n$ is the graph 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, and it has $\binom{n}{2}$ edges. The node number of edges of a complete graph states this. $K_3$ is a triangle. $K_4$ is planar, and $K_5$ is not planar. 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$.