Complete Graph — Definition, Formula & Examples

A complete graph is a graph in which every pair of distinct vertices is connected by exactly one edge. It is denoted

K_n

, where

n

is the number of vertices.

A complete graph $K_n$ is a simple, undirected graph on $n$ vertices such that for every pair of distinct vertices $u$ and $v$ , the edge $\{u, v\}$ belongs to the edge set. Equivalently, every vertex has degree $n - 1$ .

Key Formula

|E(K_n)| = \binom{n}{2} = \frac{n(n-1)}{2}

Where:

$n$ = Number of vertices in the complete graph
$|E(K_n)|$ = Number of edges in the complete graph

How It Works

To construct

K_n

, place

n

vertices and draw an edge between every possible pair. Because no vertex is left unconnected to any other, the graph has the maximum number of edges a simple graph on

n

vertices can have. Complete graphs serve as a benchmark in graph theory: any simple graph on

n

vertices is a subgraph of

K_n

Worked Example

Problem: How many edges does the complete graph K_6 have?

Apply the formula: Substitute n = 6 into the edge-count formula.

|E(K_6)| = \frac{6(6-1)}{2} = \frac{6 \cdot 5}{2}

Compute: Simplify the arithmetic.

= \frac{30}{2} = 15

Answer:

K_6

has 15 edges.

Why It Matters

Complete graphs appear throughout combinatorics and computer science. Ramsey theory asks how large a complete graph must be before a monochromatic substructure is guaranteed. In networking,

K_n

models a fully connected topology where every node can communicate directly with every other node.

Common Mistakes

Mistake: Confusing a complete graph with a connected graph.

Correction: A connected graph merely requires a path between every pair of vertices; a complete graph requires a direct edge between every pair. Every complete graph is connected, but most connected graphs are not complete.