Petersen Graph - Embeddings

Embeddings

The Petersen graph is nonplanar. Any nonplanar graph has as minors either the complete graph, or the complete bipartite graph, but the Petersen graph has both as minors. The minor can be formed by contracting the edges of a perfect matching, for instance the five short edges in the first picture. The 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. Thus, the Petersen graph has crossing number 2. 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. 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.