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 can be generalized, with the resulting graphs being known as generalized Petersen graphs for and . The Petersen graph corresponds to .
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).
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 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 following table summarizes some properties of the Petersen graph.
|automorphism group order||120|
|graph complement name||5-triangular graph|
|edge chromatic number||4|
|Hamiltonian cycle count||0|
|Hamiltonian path count||240|
|line graph name||quartic vertex-transitive graph Qt39|
|perfect matching graph||yes|
|strongly regular graph|