Petersen graph
Related graphs

The generalized Petersen graph G (n, k) {\displaystyle G(n,k)} is formed by connecting the vertices of a regular n -gon to the corresponding vertices of a star polygon with Schläfli symbol { n / k }. For instance, in this notation, the Petersen graph is G (5, 2) {\displaystyle G(5,2)}: it can be formed by connecting corresponding vertices of a pentagon and five-point star, and the edges in the star connect every second vertex. The generalized Petersen graphs also include the n -prism G (n, 1) {\displaystyle G(n,1)} the Dürer graph G (6, 2) {\displaystyle G(6,2)}, the Möbius-Kantor graph G (8, 3) {\displaystyle G(8,3)}, the dodecahedron G (10, 2) {\displaystyle G(10,2)}, the Desargues graph G (10, 3) {\displaystyle G(10,3)} and the Nauru graph G (12, 5) {\displaystyle G(12,5)}.

The Petersen family consists of the seven graphs that can be formed from the Petersen graph by zero or more applications of Δ-Y or Y-Δ transforms. The complete graph K is also in the Petersen family. These graphs form the forbidden minors for linklessly embeddable graphs, graphs that can be embedded into three-dimensional space in such a way that no two cycles in the graph are linked.

The Clebsch graph contains many copies of the Petersen graph as induced subgraphs: for each vertex v of the Clebsch graph, the ten non-neighbors of v induce a copy of the Petersen graph.
length_constraints:number_words[304]