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.

Contents

1 Properties 1.1 Basic properties 1.2 Other properties 1.3 Largest and smallest 2 As counterexample 3 Generalized Petersen graph 4 Petersen graph family 5 References 6 External links

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. See the glossary.
• 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.)

Other properties

The Petersen graph ...

• is nonplanar, since it has a subgraph homeomorphic to complete bipartite graph K_3,3 (see Kuratowski's theorem).
• is nonplanar, since it has the complete graph K₅ as a minor (contract the five short edges in the first picture).
• has crossing number 2.
• has a Hamiltonian path but no Hamiltonian cycle.
• is symmetric, meaning that it is edge transitive and vertex transitive.
• is hypohamiltonian , meaning that although it has no Hamiltonian cycle, deleting any vertex makes it Hamiltonian.
• is one of only 14 cubic distance-regular graphs .
• is the complement of the line graph of K₅.
• is the only (connected) cubic graph of girth 5, making it the only (3,5)-cage graph and the only (3,5)-Moore graph .
• 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₅.
• is the Kneser graph K_5,2.
• 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 largest cubic graph with diameter 2.
• is the smallest hypohamiltonian 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

The generalized Petersen graph G(n,k) is a graph with vertex set and edge set where subscripts are to be read modulo n and k < n / 2. The Petersen graph itself is G(5,2). This important and well known family of graphs that was introduced in 1969 by Mark Watkins possesses a number of interesting properties. For example,

1. G(n,r) is vertex-transitive if and only if n = 10,r = 2 or .
2. It is a Cayley graph if and only if .
3. It is arc-transitive only in the following seven cases: (n,r) = (4,1),(5,2),(8,3),(10,2),(10,3),(12,5),(24,5).

The family contains some very important graphs. Among others 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), the Desargues graph G(10,3), etc.

Petersen graph family

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

References

• Available on Google print.
• Mitch Keller,
• 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.

External links

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