Petersen Graph
"The" Petersen graph is the graph 
, illustrated
above in several embeddings (D'Angelo and West 2000, p. 229), possessing ten
nodes, all of whose nodes have degree three (Saaty and
Kainen 1986; Harary 1994, p. 89; Knuth 2008, p. 39).
The Petersen graph is implemented in the Wolfram Language as PetersenGraph[] and GraphData["PetersenGraph"].
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 
.
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 non-Hamiltonian. 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 non-Hamiltonian.
In fact, it is also the smallest hypohamiltonian
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).
It is also a unit-distance graph (Gerbracht 2008).
The Petersen graph is the only smallest-girth graph which has no Tait coloring, and is the unique 
-cage
graph (Harary 1994, p. 175), as well as the unique 
-Moore
graph. 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 can be generalized, and the resulting graph is known, not surprisingly, as a generalized Petersen graph 
(for 
and 
).
The Petersen graph provides a 6-coloring of the projective plane.
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 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 |
Contact the MathWorld Team
petersen graph
