 TOPICS  # Petersen Graph 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 (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

Cage Graph, Generalized Petersen Graph, Girth, Hoffman-Singleton Graph, Hypohamiltonian Graph, Integral Graph, Kneser Graph, Moore Graph, Odd Graph, Petersen Family Graphs, Smallest Cubic Crossing Number Graph

## Explore with Wolfram|Alpha More things to try:

## References

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 236 and 243, 1976.Brouwer, A. E. "The Petersen Graph." http://www.win.tue.nl/~aeb/drg/graphs/Petersen.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, pp. 104 and 209, 1989.Clancy, K.; Haythorpe, M.; Newcombe, A.; and Pegg, E. Jr. "There Are No Cubic Graphs on 26 Vertices with Crossing Number 10 or 11." Preprint. 2019.Clark, L. and Entringer, R. "Smallest Maximally Nonhamiltonian Graphs." Periodica Math. Hungarica 14, 57-68, 1983.D'Angelo, J. P. and West, D. B. Mathematical Thinking: Problem-Solving and Proofs, 2nd ed. Upper Saddle River, NJ: Prentice-Hall, 2000.DistanceRegular.org. "Petersen Graph  ." http://www.distanceregular.org/graphs/petersen.html.Exoo, G. "Rectilinear Drawings of Famous Graphs: The Petersen Graph." http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/pete.gif.Gerbracht, E. H.-A. "On the Unit Distance Embeddability of Connected Cubic Symmetric Graphs." Kolloquium über Kombinatorik. Magdeburg, Germany. Nov. 15, 2008.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 89, 112, and 175, 1994.Hoffman, A. J. and Singleton, R. R. "On Moore Graphs of Diameter Two and Three." IBM J. Res. Develop. 4, 497-504, 1960.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Horvat, B. and Pisanski, T. "Unit Distance Representations of the Petersen Graph in the Plane." To appear in Ars Combin..Knuth, D. E. The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Functions and Boolean Functions.. Upper Saddle River, NJ: Addison-Wesley, 2008.Nedela, R. and Škoviera, M. "Which Generalized Petersen Graphs Are Cayley Graphs?" J. Graph Th. 19, 1-11, 1995.Pegg, E. Jr. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 161-170, 2009. https://www.mathematica-journal.com/data/uploads/2009/11/CrossingNumberGraphs.pdf.Petersen, J. "Sur la théorème de Tait." L'Intermédiare des Math. 5, 225-227, 1898.Punnim, N.; Saenpholphat, V.; and Thaithae, S. "Almost Hamiltonian Cubic Graphs." Int. J. Comput. Sci. Netw. Security 7, 83-86, 2007.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 271 and 276, 1998.Royle, G. "F010A." http://www.csse.uwa.edu.au/~gordon/foster/F010A.html.Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 102, 1986.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 139, 162, and 191, 1990.Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. New York: Springer, pp. 90-91, 2008.Steimle, A. and Staton, W. "The Isomorphism Classes of the Generalized Petersen Graphs." Disc. Math. 309, 231-237, 2009.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 225, 2000.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1032, 2002.Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982.

## Cite this as:

Weisstein, Eric W. "Petersen Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PetersenGraph.html