Complete Graphs, Cycles, and Wheels
You'll learn: How to identify and work with three fundamental families of graphs that appear repeatedly in graph theory.
The Core Idea
After learning the basic building blocks of graphs, mathematicians have identified certain "standard" graph structures that pop up so often they deserve special names and notation. Think of these as the "LEGO sets" of graph theory—predefined patterns you can reference instead of describing every edge individually.
Complete Graphs (Kₙ)
A complete graph Kₙ has n vertices where every vertex connects to every other vertex exactly once. It's the most "connected" simple graph possible.
- K₃ is a triangle (3 vertices, 3 edges)
- K₄ has 4 vertices with 6 edges (every pair connected)
- In general, Kₙ has n(n-1)/2 edges
Analogy: Imagine a group of n friends where everyone knows everyone else—that's Kₙ.
Cycle Graphs (Cₙ)
A cycle graph Cₙ has n vertices arranged in a closed loop, where each vertex connects to exactly two neighbors, forming a circular path.
- C₃ is a triangle
- C₄ is a square
- C₅ is a pentagon, and so on
Each vertex has degree 2, and there are exactly n edges.
Analogy: Think of people standing in a circle holding hands—that's a cycle graph.
Wheel Graphs (Wₙ)
A wheel graph Wₙ is formed by taking a cycle Cₙ and adding one central "hub" vertex connected to all vertices in the cycle.
- W₃ looks like a pyramid viewed from above
- W₄ resembles a wheel with 4 spokes
- Wₙ has n+1 vertices and 2n edges
Analogy: Picture a bicycle wheel with spokes connecting the rim to the center hub.
Key Takeaway: Complete graphs (Kₙ), cycles (Cₙ), and wheels (Wₙ) are fundamental graph families with predictable structures, allowing mathematicians to reference complex patterns with simple notation.