The Petersen graph is the ultimate troublemaker of the mathematical world
In short: With just ten vertices and fifteen edges, this small structure consistently defies expectations. It serves as a vital counterexample to countless optimistic theories in graph theory. From its unique symmetries to its refusal to follow standard Hamiltonian rules, the Petersen graph remains an essential, if frustrating, benchmark for mathematicians.
First appearing in an 1886 paper by A. B. Kempe, the graph was later named after Julius Petersen, who utilized it in 1898 to demonstrate the smallest cubic graph lacking a three-edge coloring. It is a highly symmetric object, being both edge-transitive and vertex-transitive. Despite this, it holds the distinction of being the most compact vertex-transitive graph that cannot be represented as a Cayley graph.
The graph is famously non-planar, meaning it cannot be drawn on a flat surface without at least two edges crossing. While it lacks a Hamiltonian cycle—a path visiting every vertex exactly once—it is classified as hypohamiltonian because removing any single vertex makes the remaining structure Hamiltonian. This makes it a rare specimen; only five such connected vertex-transitive graphs are currently known to exist.
Beyond its structural quirks, the Petersen graph is a foundational element in broader mathematical fields. It is the smallest snark—a bridgeless cubic graph requiring four colors for its edges—and it acts as a forbidden minor for linklessly embeddable graphs. Its influence extends into tropical geometry and the study of non-orientable surfaces, where it can be embedded on a projective plane without any crossings.
Donald Knuth famously described the configuration as a remarkable tool for dismantling optimistic predictions about graph behavior. Because it is a strongly regular graph with a girth of five, it serves as the unique (3,5)-Moore graph. Whether appearing as a pentagram within a pentagon or as a hemi-dodecahedron, this ten-vertex structure continues to challenge and refine our understanding of discrete mathematics.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Petersen graph
To cite this card, link to https://intellectplus.co.uk/app/science-petersen-graph.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Discrete mathematics · More in Science · Latest · A–Z · All topics