Complete Graphs (Kₙ) — Graph Theory

Overview

What this concept solves

A complete graph Kₙ joins every single pair of vertices — it is the densest simple graph that can exist on n vertices. There is no pair left unconnected, no vertex that doesn't touch every other. Drawn on a circle it looks like a perfectly woven web; add one more vertex and a whole new fan of edges sprouts from it to every vertex already there. Nothing is missing, which is exactly what makes it special.

Because every pair is joined, Kₙ has exactly n(n−1)/2 edges and every vertex has the same degree n−1. Those two numbers are the whole story. K₅ has 10 edges; K₆ has 15; K₁₀ has 45; K₁₀₀ already has 4,950. The edge count grows quadratically — roughly with n² — so doubling the vertices roughly quadruples the edges. That quadratic blow-up is why the complete graph is the worst case nearly every graph algorithm secretly fears.

You rarely want a fully complete graph in the wild — real networks are sparse. But Kₙ matters as a benchmark and a bound. It is the maximum any simple graph on n vertices can reach, so 'how dense is this graph?' is answered by comparing its edge count to n(n−1)/2. It is the structure that makes an adjacency matrix pay off, the worst case for the travelling-salesman tour, and the shape a clique becomes when a group is completely interconnected.

Mechanics

How it works

The two numbers that define Kₙ

Edge count = n(n−1)/2. Pick any vertex: it connects to the other n−1. Do that for all n vertices and you count n(n−1) endpoints — but every edge has two endpoints, so each edge got counted twice. Divide by 2: n(n−1)/2.
Degree = n−1 for every vertex. Each vertex is joined to all the others and to no more, so the graph is regular — every vertex has identical degree. (Sanity check via the handshake lemma: Σ deg = n·(n−1) = 2·|E|, so |E| = n(n−1)/2 again.)
It's the upper bound. A simple graph on n vertices can have at most n(n−1)/2 edges, and Kₙ is the graph that hits it. Any more would require a self-loop or a parallel edge — and then it's no longer simple.

Quadratic growth

n(n−1)/2 is Θ(n²) — for large n it behaves like n²/2. That single fact drives a lot of algorithm design. Listing or even just touching every edge is O(n²) work. An algorithm that's O(V + E) on a sparse graph degrades to O(V²) on a complete one, and an O(V·E) algorithm becomes O(V³). When someone reports an algorithm's worst case, they are very often imagining it running on Kₙ.

When the matrix finally wins

An adjacency list costs O(V + E) space and beats the O(V²) adjacency matrix on the sparse graphs you usually meet. But on Kₙ, E itself is Θ(V²) — the list saves nothing and carries per-node pointer overhead, while the matrix is a tight, cache-friendly V×V block. Dense ⇒ matrix. The complete graph is the cleanest case where that rule of thumb flips.

Cliques are complete subgraphs

A clique is a set of vertices that are all mutually connected — i.e. they induce a complete subgraph. So a clique of size k is just a Kₖ hiding inside a bigger graph. Finding the largest clique (the maximum clique problem) is NP-hard precisely because completeness is a demanding, all-or-nothing condition.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Complete Graphs (Kₙ)

About this simulation

A complete graph Kₙ across four tabs, with a slider to choose n. Build Kₙ lays the vertices on a circle and draws every pair one edge at a time, narrating the running count toward the total; Counting the edges derives the n(n−1)/2 formula by walking each vertex's degree; Density extreme contrasts Kₙ's quadratic edge count against a sparse tree on the same vertices. Free play gives you the n slider (2–10) with live relayout, a Show all / Clear toggle, and live stats for n, the edge count, and the formula.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Build Kₙ

On the Build Kₙ tab the vertices sit on a circle. Press Play to draw every pair one edge at a time; each step names the pair being joined and the side panel shows edges drawn so far / total. Watch the count march toward n(n−1)/2 and land exactly on it when the last pair is connected — at K₆ that's the 15th edge. Use Step / Back to add or remove a single edge.

try 02

Counting the edges

Switch to Counting the edges and Play. The prototype walks each vertex and notes it connects to the other n−1, accumulating n·(n−1) in the side panel. The final step halves it: every edge was counted from both endpoints, so divide by 2 — giving n(n−1)/2. Confirm each vertex's degree reads n−1, and that the formula stat equals the edge count.

try 03

Density extreme

On Density extreme, Play to see Kₙ's n(n−1)/2 edges contrasted against a sparse tree on the same n vertices, which needs only n−1. The side panel shows Kₙ edges vs tree edges side by side. Notice how the gap explodes as n grows — quadratic versus linear — which is exactly why a dense graph favours an adjacency matrix over a list.

try 04

Free play — drag the slider, watch it explode

Open Free play and drag the n slider from 2 to 10; the circle relayouts live and rebuilds Kₙ. Toggle Show all / Clear to draw or hide all edges. Watch the edges and n(n−1)/2 stats stay locked together and grow far faster than n itself — go from n=5 (10 edges) to n=10 (45 edges) and feel the quadratic jump.

In practice

When to use it — and what you give up

Reach for a complete graph when

Every pair genuinely interacts — a round-robin tournament where each team plays every other, an all-to-all message exchange, a fully-meshed network where every node links directly to every other.
You need a worst-case benchmark — to stress-test an algorithm or prove a bound, Kₙ is the maximal, most adversarial input on n vertices.
You're reasoning about cliques — detecting fully-interconnected groups (a friend group where everyone knows everyone, co-occurring terms) means searching for complete subgraphs.
The graph really is dense — when E approaches n(n−1)/2, store it as an adjacency matrix rather than a list.

Avoid forcing completeness when

The real network is sparse — most graphs (roads, the web, social follows) have far fewer than n²/2 edges; modelling them as complete wastes Θ(n²) space and erases the structure you care about.
You only need some connections — if not every pair interacts, a general graph with the actual edges is both smaller and more faithful.
n is large — n(n−1)/2 explodes; a complete graph on 100k vertices is ~5 billion edges, which no list or matrix will hold.

Pros

Maximally connected — there's a direct edge between every pair, so the diameter is 1 and any vertex reaches any other in a single hop.
Perfectly regular and predictable — every vertex has the same degree n−1, and the edge count is exactly n(n−1)/2, with no shape-dependent variation.
Robust — you can delete many edges or vertices and the rest stays connected; there is no single point of failure.
The natural upper bound — gives a clean denominator for measuring any graph's density and a concrete worst case for analysis.

Cons

Quadratic edge count — n(n−1)/2 = Θ(n²) edges make storage and any all-edges algorithm expensive as n grows.
Almost never realistic — real-world relationships are sparse; true all-to-all connectivity is rare and usually wasteful.
Expensive to maintain — a fully-meshed network needs n−1 links per node, so adding one node forces n new connections.
The algorithmic worst case — traversals, shortest paths, and tour problems all hit their worst running times on Kₙ.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

complete-graph.ts

// The complete graph K_n: every pair of vertices is joined.
// Densest simple graph possible — n(n-1)/2 edges, every degree n-1.
class CompleteGraph {
  readonly n: number;
  readonly vertices: number[];

  constructor(n: number) {
    if (n < 0) throw new Error("n must be non-negative");
    this.n = n;
    this.vertices = Array.from({ length: n }, (_, i) => i);
  }

  // All unordered pairs {i, j} with i < j — exactly the edges of K_n.
  *edges(): IterableIterator<[number, number]> {
    for (let i = 0; i < this.n; i++)
      for (let j = i + 1; j < this.n; j++) yield [i, j];
  }

  // n(n-1)/2 — derived, not counted.
  edgeCount(): number {
    return (this.n * (this.n - 1)) / 2;
  }

  // Every vertex touches all the others, so the graph is (n-1)-regular.
  degree(_v: number): number {
    return this.n - 1;
  }

  // Place vertices evenly on a circle so K_n draws as a symmetric web.
  layout(cx = 280, cy = 145, radius = 120): Array<[number, number]> {
    return this.vertices.map((i) => {
      const angle = -Math.PI / 2 + (i * 2 * Math.PI) / this.n;
      return [cx + radius * Math.cos(angle), cy + radius * Math.sin(angle)];
    });
  }

  // Density: how close another graph's edge count is to the K_n ceiling.
  static density(vertices: number, edges: number): number {
    const max = (vertices * (vertices - 1)) / 2;
    return max === 0 ? 0 : edges / max; // 1.0 means complete
  }
}

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

How many edges does the complete graph K₈ have?

question 02 / 03

In Kₙ, what is the degree of every vertex, and why is it the same for all of them?

question 03 / 03

Why is the complete graph the worst case for many graph algorithms?

0/3 answered