Complete graph
= Complete graph
{title2=$K_n$}
{wiki}
A <complete graph> is a <simple graph> in which every two distinct <vertices> are joined by an <edge>. The finite <complete graph> on $n$ <vertices> is denoted $K_n$. Here the <edges> are undirected, and <self-loops> are excluded. The usual pictures below use $n\geq1$: $K_1$ is a single <vertex>, $K_2$ a single <edge>, and $K_3$ a <triangle in a graph>.<Graph Theory by Reinhard Diestel>[§1.1, printed p. 3 of the third electronic edition (2005): pairwise adjacency, complete graphs and triangle notation]{ref}
Completeness describes all the possible pairs, rather than a drawing style. Different layouts can represent the same <graph> through a <graph isomorphism>. Crossing lines away from the drawn <vertices> do not add new <vertices> or <edges>.
\Image[/complete-graphs-small-orders.png]
{title=Complete graphs with one through five vertices}
{description=Each original drawing joins every pair of distinct <vertices> exactly once. The <complete graphs> $K_1,K_2,K_3,K_4,K_5$ have respectively $0,1,3,6,10$ <edges>. Intersections of drawn lines in the $K_5$ panel are not additional <vertices>.}
There are $\binom n2=n(n-1)/2$ unordered pairs of distinct <vertices>, so this is the <edge count of a complete graph>. Each <vertex> has <vertex degree> $n-1$. The <degree-sum formula> gives the same count: $2|E|=n(n-1)$. These formulas make a <complete graph> the upper extreme for <edge> counts among <simple graphs> of a fixed size.
This is useful when modelling pairwise relationships. If every pair of objects needs its own direct connection, ten <vertices> require $45$ <edges>, while twenty require $190$. Adding one more <vertex> to $K_n$ introduces $n$ further <edges>. This counts a specified direct-link model; it does not require every communication system to implement every relationship with a separate physical connection.
A <proper vertex coloring> of $K_n$ must give every <vertex> a different color, so its <chromatic number> is $n$. For $n\geq1$, its <independence number> is $1$: two distinct <vertices> already have an <edge> between them. Thus <complete graphs> provide immediate test cases for <graph coloring> and <independent sets>.