Complete Graph is Regular

Theorem

Let $K_p$ be the complete graph of order $p$.

Then $K_p$ is $p-1$-regular.

Proof

By definition of complete graph, $K_p$ has $p$ vertices.

Also by definition of complete graph, each vertex of $K_p$ is adjacent to all the other $p - 1$ vertices of $K_p$.

As $K_p$ is a simple graph, there can be only one edge joining any pair of vertices of $K_p$.

So each vertex of $K_p$ has $p - 1$ edges to which it is incident.

So, by definition, $K_p$ is $p-1$-regular.

$\blacksquare$

Examples

Complete Graph $K_5$

The complete graph $K_5$ of order $5$ is $4$-regular.

Sources

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.1$: The Degree of a Vertex