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
drawings (cf. Bermond et al. 1986; Saaty and Kainen 1986; Harary 1994, p. 89;
D'Angelo and West 2000; West 2000, p. 229; Knuth 2008, p. 39).
The edges of the Petersen graph serve as the colors in a Petersen coloring.
The Petersen graph is illustrated above in some drawings involving curved edges (cf. Elspas 1964; Bondy and Murty 1976, Ex. 1.2.6, p. 6; Bermond et al. 1986; Kochol 1996).
The Petersen graph is also the smallest 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 E. 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, graph 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-graph cycle 
, then the graph consists of 
plus five chords. If each chord joins
vertices opposite on 
, then there is a 4-graph cycle.
Hence some chord 
joins vertices at graph
distance 4 along 
.
Now no chord incident to a vertex opposite an endpoint
of 
on 
can be added without creating a graph 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. 2020).
Its projective plane crossing number is 0, so it is a projective planar graph.
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) and a platypus graph. In fact, the Petersen graph and the Petersen graph with one edge removed are the two smallest girth-5 platypus graphs (Goedgebeur et al. 2020).
It is also a unit-distance graph (Gerbracht 2008).
The Petersen graph has no Tait coloring. It is the graph 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 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-map 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"].
."
