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 . Its vertex set is the set of all 2-element subsets of , 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 . Count the subsets.
Step 2: Take any vertex, for example . Its neighbors are the 2-element subsets that avoid both 1 and 2. They must come from the remaining set : these are , and . The same count holds for every vertex, so the graph is 3-regular.
Step 3: Apply the handshake lemma. The degrees sum to twice the number of edges.
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 . The Petersen graph has edges, so it cannot be planar. It also contains a subdivision of .
