Exercise 238Combinatorics › Graph theoryHigh schoolAdded 3 Nov 2026

The complete graph $K_n$

#complete graph#edges#degree

Statement

The complete graph $K_n$ has all pairs of distinct vertices connected. Give its order, size, and the degree of each vertex.

Hint

Each pair of vertices forms one edge.

Show solutionHide solution

Order. $n$ vertices.

Size. $\binom{n}{2}=\frac{n(n-1)}{2}$ edges.

Degree. Each vertex is connected to all $n-1$ others: $\deg(v)=n-1$ for all $v$ .

Check. Sum of degrees $=n(n-1)=2|E|$ . ✓

Conclusion. $|V|=n$ , $|E|=\binom{n}{2}$ , regular of degree $n-1$ .