Complete Graphs
What You'll Learn
You'll discover what makes a graph "complete" and explore the fundamental combinatorial properties that define these maximally-connected structures.
What is a Complete Graph?
A complete graph is a simple graph where every single pair of distinct vertices is connected by exactly one edge. In other words, if you have n vertices, every vertex connects directly to every other vertex—no exceptions.
Think of it like a dinner party where everyone has personally met and shaken hands with everyone else. No strangers, no missing connections.
Notation and Structure
Complete graphs are denoted as K_n, where n is the number of vertices:
- K₃: A triangle (3 vertices, 3 edges)
- K₄: Four vertices where each connects to the other three (6 edges)
- K₅: Five vertices, all interconnected (10 edges)
Notice that complete graphs are always simple graphs—no self-loops and no multiple edges between the same pair of vertices.
The Edge Count Formula
Here's the key combinatorial property: How many edges does K_n have?
Since each vertex connects to every other vertex exactly once, we're choosing 2 vertices from n vertices:
Number of edges = n(n-1)/2
- K₃: 3(2)/2 = 3 edges
- K₄: 4(3)/2 = 6 edges
- K₅: 5(4)/2 = 10 edges
- K₁₀₀: 100(99)/2 = 4,950 edges
This quadratic growth means complete graphs become extremely dense very quickly. In adjacency matrix representation, K_n is nearly all 1s (except the diagonal).
Properties
- Every vertex has degree n-1 (connected to all others)
- Always connected (you can reach any vertex from any other)
- Contains every possible simple subgraph on n vertices
Key Takeaway: A complete graph K_n connects every pair of its n vertices with exactly one edge, resulting in n(n-1)/2 total edges—the maximum possible for a simple graph.