Petersen graph

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring. Although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in a paper by A. B. Kempe (1886). Kempe observed that its vertices can represent the ten lines of the Desargues configuration, and its edges represent pairs of lines that do not meet at one of the ten points of the configuration. Donald Knuth states that the Petersen graph is "a remarkable configuration that serves as a counterexample to many optimistic predictions about what might be true for graphs in general." The Petersen graph also makes an appearance in tropical geometry. The cone over the Petersen graph is naturally identified with the moduli space of five-pointed rational tropical curves.

Constructions

The Petersen graph is the complement of the line graph of K5. It is also the Kneser graph KG5,2; this means that it has one vertex for each 2-element subset of a 5-element set, and two vertices are connected by an edge if and only if the corresponding 2-element subsets are disjoint from each other. As a Kneser graph of the form KG2n−1,n−1 it is an example of an odd graph. Geometrically, the Petersen graph 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.

Embeddings The Petersen graph is nonplanar. Any nonplanar graph has as minors either the complete graph K5, or the complete bipartite graph K3,3, but the Petersen graph has both as minors. The K5 minor can be formed by contracting the edges of a perfect matching, for instance the five short edges in the first picture. The K3,3 minor can be formed by deleting one vertex (for instance the central vertex of the 3-symmetric drawing) and contracting an edge incident to each neighbor of the deleted vertex.

The most common and symmetric plane drawing of the Petersen graph, as a pentagram within a pentagon, has five crossings. However, this is not the best drawing for minimizing crossings; there exists another drawing (shown in the figure) with only two crossings. Because it is nonplanar, it has at least one crossing in any drawing, and if a crossing edge is removed from any drawing it remains nonplanar and has another crossing; therefore, its crossing number is exactly 2. Each edge in this drawing is crossed at most once, so the Petersen graph is 1-planar. On a torus the Petersen graph can be drawn without edge crossings; it therefore has orientable genus 1.

The Petersen graph can also be drawn (with crossings) in the plane in such a way that all the edges have equal length. That is, it is a unit distance graph. The simplest non-orientable surface on which the Petersen graph can be embedded without crossings is the projective plane. This is the embedding given by the hemi-dodecahedron construction of the Petersen graph (shown in the figure). The projective plane embedding can also be formed from the standard pentagonal drawing of the Petersen graph by placing a cross-cap within the five-point star at the center of the drawing, and routing the star edges through this cross-cap; the resulting drawing has six pentagonal faces. This construction forms a regular map and shows that the Petersen graph has non-orientable genus 1.

Symmetries The Petersen graph is strongly regular (with signature srg(10,3,0,1)). It is also symmetric, meaning that it is edge transitive and vertex transitive. More strongly, it is 3-arc-transitive: every directed three-edge path in the Petersen graph can be transformed into every other such path by a symmetry of the graph. It is one of only 13 cubic distance-regular graphs. The automorphism group of the Petersen graph is the symmetric group S5; the action of S5 on the Petersen graph follows from its construction as a Kneser graph. The Petersen graph is a core: every homomorphism of the Petersen graph to itself is an automorphism. As shown in the figures, the drawings of the Petersen graph may exhibit five-way or three-way symmetry, but it is not possible to draw the Petersen graph in the plane in such a way that the drawing exhibits the full symmetry group of the graph. Despite its high degree of symmetry, the Petersen graph is not a Cayley graph. It is the smallest vertex-transitive graph that is not a Cayley graph.

Hamiltonian paths and cycles

… excerpt ends here. Continue reading the full article.