Mathwords logoMathwords

Petersen Graph — Definition & Example

The Petersen graph is a specific graph with 10 vertices and 15 edges. It is usually drawn as an outer pentagon joined by five spokes to an inner five-pointed star. It breaks so many plausible-sounding conjectures that graph theorists use it as a standard first test case for new claims.

The Petersen graph is the Kneser graph KG(5,2)KG(5,2). Its vertex set is the set of all 2-element subsets of {1,2,3,4,5}\{1,2,3,4,5\}, and two vertices are adjacent if and only if their subsets are disjoint. Up to isomorphism, it is the unique 3-regular graph of girth 5 on 10 vertices. It has diameter 2, chromatic number 3, and chromatic index 4. It is non-planar and has no Hamiltonian cycle.

Worked Example

Problem: Use the Kneser definition to show that the Petersen graph has 10 vertices, that every vertex has degree 3, and that it has 15 edges.
Step 1: Each vertex is a 2-element subset of {1,2,3,4,5}\{1,2,3,4,5\}. Count the subsets.
∣V∣=(52)=10|V| = \binom{5}{2} = 10
Step 2: Take any vertex, for example {1,2}\{1,2\}. Its neighbors are the 2-element subsets that avoid both 1 and 2. They must come from the remaining set {3,4,5}\{3,4,5\}: these are {3,4}\{3,4\}, {3,5}\{3,5\} and {4,5}\{4,5\}. The same count holds for every vertex, so the graph is 3-regular.
deg⁡(v)=(32)=3\deg(v) = \binom{3}{2} = 3
Step 3: Apply the handshake lemma. The degrees sum to twice the number of edges.
∣E∣=10⋅32=15|E| = \frac{10 \cdot 3}{2} = 15
Answer: The Petersen graph has 10 vertices, every vertex has degree 3, and it has 15 edges.

Why It Matters

In an undergraduate graph theory course, the Petersen graph is the go-to counterexample. It is the smallest snark: a bridgeless 3-regular graph whose edges cannot be properly colored with 3 colors. This connects it to research on the Four Color Theorem. It is also vertex-transitive but not a Cayley graph, and it has no Hamiltonian cycle even though deleting any single vertex leaves a graph that has one.

Common Mistakes

Mistake: Claiming the Petersen graph is non-planar because the standard pentagon-and-star drawing has crossings.
Correction: A drawing with crossings proves nothing, since another drawing might avoid them. Use a real argument instead. A connected planar graph with girth 5 satisfies ∣E∣≤5(∣V∣−2)3=403|E| \le \frac{5(|V|-2)}{3} = \frac{40}{3}. The Petersen graph has 15>40315 > \frac{40}{3} edges, so it cannot be planar. It also contains a subdivision of K3,3K_{3,3}.

Related Terms

  • Cubic Graph — The kind of graph where every vertex has three edges
  • Cayley Graph — Petersen graph is the classic non-Cayley vertex-transitive graph
  • Bipartite Graph — Petersen fails this test because its pentagon is an odd cycle
  • Clique — Petersen graph has no triangles, so its largest clique has size 2
  • Acyclic Graph — Contrasts with Petersen, whose shortest cycles have length 5
  • Graph Theory — Branch of mathematics that studies graphs like this one
  • Counterexample — Petersen graph often serves as one for conjectures