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 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 (Gerbracht2008).
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 Petersengraph is the Desargues graph.
The line graph of the Petersen graph is the quarticvertex-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 projectiveplane.
The seven graphs obtainable from the complete graph by repeated triangle-Y exchanges are also called Petersen graphs, where the three graph edges forming the triangle are replaced by three graph edges and a new graph vertex that form a Y, and the reverse operation is also permitted. A graph is intrinsically linked iff it contains one of the seven Petersen graphs (Robertson et al. 1993).
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.
|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|