Petersen graph

The Petersen graph is most commonly drawn as a pentagon with a star inside, with five spokes.

The Petersen graph has crossing number 2.

The Petersen graph is a unit-distance graph: it can be drawn in the plane with each edge having unit length.

The Petersen graph is a small graph that serves as a useful example and counterexample in graph theory. It was first published by Julius Petersen in 1898. Petersen constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

Properties

Basic properties

The Petersen graph ...

• is 3-connected and hence 3-edge-connected and bridgeless. See the glossary.
• has independence number 4 and is 3-partite. See the glossary.
• is cubic, is strongly regular, has domination number 3, and has a perfect matching and a 2-factor. See the glossary.
• has radius 2 and diameter 2.
• has chromatic number 3 and chromatic index 4, making it a snark. (To see that there is no 3-edge-coloring requires checking four cases.) It was the only known snark from 1898 until 1946.

Other properties

The Petersen graph ...

• is nonplanar. It has as minors both the complete graph $K_{5}$ (contract the five short edges in the first picture), and the complete bipartite graph $K_{3,3}$.
• has crossing number 2.
• has a Hamiltonian path but no Hamiltonian cycle.
• is symmetric, meaning that it is edge transitive and vertex transitive.
• is one of only five known vertex transitive graphs with no Hamiltonian cycle. It is conjectured that there are no others.
• is hypohamiltonian, meaning that although it has no Hamiltonian cycle, deleting any vertex makes it Hamiltonian. See this embedding for a demonstration of the hypohamiltonian property.
• is one of only 14 cubic distance-regular graphs.
• is the complement of the line graph of $K_{5}$.
• is a unit-distance graph, meaning it can be drawn in the plane with all the edges length 1.
• has automorphism group the symmetric group $S_{5}$.
• is the Kneser graph $KG_{5,2}$. (This means you get the Petersen graph from the following construction: Take the 2-element subsets of a 5-element set as vertices, and connect two vertices if they are disjoint as sets.)
• is the graph formed by the vertices and edges of the hemi-dodecahedron, that is, a dodecahedron with opposite points, lines and faces identified together.
• has graph spectrum −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.

Every homomorphism of the Petersen graph to itself that doesn't identify adjacent vertices is an automorphism.

Largest and smallest

The Petersen graph ...

• is the smallest snark.
• is the smallest bridgeless cubic graph with no Hamiltonian cycle.
• is the smallest bridgeless cubic graph with no three-edge-coloring.
• is the largest cubic graph with diameter 2.
• is the smallest hypohamiltonian graph.
• is the smallest cubic graph of girth 5. (It is the unique $(3,5)$-cage graph. In fact, since it has only 10 vertices, it is the unique $(3,5)$-Moore graph.)

As counterexample

The Petersen graph frequently arises as a counterexample or exception in graph theory. For example, if G is a 2-connected, r-regular graph with at most 3r + 1 vertices, then G is Hamiltonian or G is the Petersen graph (Holton page 32).

Generalized Petersen graph

In 1969 Mark Watkins introduced a family of graphs generalizing the Petersen graph. The generalized Petersen graph $G(n,k)$ is a graph with vertex set

$\{u_{0},u_{1},\dots ,u_{n-1},v_{0},v_{1},\dots ,v_{n-1}\}$

and edge set

$\{u_{i}u_{i+1},u_{i}v_{i},v_{i}v_{i+k}:i=0,\dots ,n-1\}$

where subscripts are to be read modulo $n$ and $k<n/2$.

The Petersen graph itself is $G(5,2)$.

This family of graphs possesses a number of interesting properties. For example,

1. $G(n,k)$ is vertex-transitive if and only if $n=10,k=2$ or $k^{2}\equiv \pm 1{\pmod {n}}$.
2. It is edge-transitive only in the following seven cases: $(n,k)=(4,1),(5,2),(8,3),(10,2),(10,3),(12,5),(24,5)$.
3. It is bipartite iff $n$ is even and $k$ is odd.
4. It is a Cayley graph if and only if $k^{2}\equiv 1{\pmod {n}}$.

Among the generalized Petersen graphs are the n-prism $G(n,1)$, the Dürer graph $G(6,2)$, the Möbius-Kantor graph $G(8,3)$, the dodecahedron $G(10,2)$, and the Desargues graph $G(10,3)$.

The Petersen graph itself is the only generalized Petersen graph that is not 3-edge-colorable. [Castagna and Prins, 1972]

Petersen graph family

The Petersen graph family consists of the seven graphs that can be formed from the complete graph $K_{6}$ by zero or more applications of Δ-Y or Y-Δ transforms. A graph is intrinsically linked if and only if it contains one of these graphs as a subgraph.

References

• Frank Castagna and Geert Prins (1972). "Every Generalized Petersen Graph has a Tait Coloring". Pacific Journal of Mathematics. 40.
• Geoffrey Exoo, Frank Harary, and Jerald Kabell (1981). "The crossing numbers of some generalized Petersen graphs". Mathematica Scandinavica. 48: 184–188.{{cite journal}}: CS1 maint: multiple names: authors list (link)
• D. A. Holton and J. Sheehan (June 1, 1993). The Petersen Graph. Cambridge University Press. ISBN 0521435943. {{cite book}}: Check date values in: |date= (help); External link in |title= (help) Available on Google print.
• Mitch Keller, "Kneser graphs". PlanetMath.
• László Lovász (1993). Combinatorial Problems and Exercises, second edition. North-Holland. ISBN 0-444-81504-X.
• Julius Petersen (1898). "Sur le théorème de Tait". L'Intermédiaire des Mathématiciens. 5: 225–227.
• Mark E. Watkins (1969). "A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs". Journal of Combinatorial Theory. 6: 152–164.
• Weisstein, Eric W. "Petersen Graph". MathWorld.

External links

• Cubic symmetric graphs (The Foster Census)
• The Petersen graph by Andries E. Brouwer