The Petersen graph is the cubic graph on 10 vertices and 15 edges which is the unique 
-cage graph (Harary 1994,
p. 175), as well as the unique 
-Moore graph. It can be
constructed as the graph expansion of 
with steps 1 and 2, where 
is a path graph (Biggs 1993,
p. 119). Excising an edge of the Petersen
graph gives the 4-Möbius ladder 
. It is illustrated above in several embeddings (D'Angelo
and Saaty and Kainen 1986; Harary 1994, p. 89; West 2000, p. 229; Knuth
2008, p. 39). The Petersen graph is also the 10-Lindgren-Sousselier
graph.
The graph was introduced by Petersen (1898) as a counterexample to an edge coloring problem. However, it was described twelve years earlier by Kempe (1886) as the graph whose vertices correspond to the points of the Desargues configuration and edges to pairs of points that do not lie on lines that are part of the configuration. Graphs produced from configurations in this way have been termed ordinary (line) graphs by Ed Pegg, Jr. (pers. comm., Sep. 11, 2024).
The Petersen graph can be generalized, with the resulting graphs being known as generalized Petersen graphs 
for 
and 
. The Petersen graph corresponds to 
.
The Petersen graph has girth 5, diameter 2, edge chromatic number 4, chromatic number 3, and chromatic polynomial
 |
The Petersen graph is a cubic symmetric graph and is nonplanar. The following elegant proof
due to D. West demonstrates that the Petersen graph is nonhamiltonian.
If there is a 10-cycle 
,
then the graph consists of 
plus five chords. If each chord joins vertices opposite on
, then there is a 4-cycle. Hence some
chord 
joins vertices at distance 4 along 
. Now no chord incident to a vertex opposite an endpoint of
on 
can be added without creating a cycle with at most four vertices.
Therefore, the Petersen graph is nonhamiltonian.
In fact, it is also the smallest hypohamiltonian
graph.
The Petersen graph is one of two cubic graphs on 10 nodes with smallest possible graph crossing number of 2 (the other being an unnamed graph denoted CNG 2B by Pegg and Exoo 2009), making it a smallest cubic crossing number graph (Pegg and Exoo 2009, Clancy et al. 2019).
The Petersen graph is the unique almost Hamiltonian cubic graph on 10 vertices (Punnim et al. 2007). In fact, it is also maximally nonhamiltonian (Clark and Entringer 1983).
It is also a unit-distance graph (Gerbracht 2008).
The Petersen graph is the only smallest-girth graph which has no Tait coloring, It is the complement of the line
graph of the complete graph 
(Skiena 1990, p. 139), and the odd
graph 
(Skiena 1990, p. 162).
The Petersen graph is an integral graph with graph spectrum 
.
The bipartite double graph of the Petersen graph is the Desargues graph.
The line graph of the Petersen graph is the quartic vertex-transitive graph Qt39, illustrated above in several embeddings.
 |  |
The Petersen graph is depicted on the covers of both the journals Journal of Graph Theory and Discrete Mathematics. It is also the lower right graph depicted on the cover of Harary (1994).
The Petersen graph provides a 6-coloring of the projective plane.
The Petersen graph is implemented in the Wolfram Language as PetersenGraph[] and a number of precomputed properties are available via GraphData["PetersenGraph"].
The following table summarizes some properties of the Petersen graph.
| property | value |
| automorphism group order | 120 |
| characteristic polynomial |  |
| chromatic number | 3 |
| claw-free graph | no |
| clique number | 2 |
| graph complement name | 5-triangular graph |
| diameter | 2 |
| distance-regular graph | yes |
| edge chromatic number | 4 |
| edge connectivity | 3 |
| edge count | 15 |
| edge transitive | yes |
| Eulerian graph | no |
| girth | 5 |
| Hamiltonian graph | no |
| Hamiltonian cycle count | 0 |
| Hamiltonian path count | 240 |
| hypohamiltonian graph | yes |
| hypotraceable graph | no |
| integral graph | yes |
| independence number | 4 |
| line graph | no |
| line graph name | quartic vertex-transitive graph Qt39 |
| perfect graph | no |
| perfect matching graph | yes |
| planar graph | no |
| polyhedral graph | no |
| radius | 2 |
| regular graph | yes |
| square-free graph | yes |
| strongly regular graph |  |
| symmetric graph | yes |
| traceable graph | yes |
| triangle-free graph | yes |
| vertex connectivity | 3 |
| vertex count | 10 |
| vertex transitive | yes |
."
