Generalized Petersen graph

The generalized Petersen graph family was introduced in 1950 by H. S. M. Coxeter[1] and was given its name in 1969 by Mark Watkins.

Coxeter's notation for the same graph would be {n} + {n/k}, a combination of the Schläfli symbols for the regular n-gon and star polygon from which the graph is formed.

[4] This family of graphs possesses a number of interesting properties.

[10] The girth of G(n, k) is at least 3 and at most 8, in particular:[11] A table with exact girth values: Generalized Petersen graphs are regular graphs of degree three, so according to Brooks' theorem their chromatic number can only be two or three.

The Petersen graph, being a snark, has a chromatic index of 4: its edges require four colors.

All other generalized Petersen graphs have chromatic index 3.

[14] All admissible matrices of all perfect 2-colorings of the graphs G(n, 2) and G(n, 3) are enumerated.

The Dürer graph G (6, 2) .
One of the three Hamiltonian cycles in G (9, 2). The other two Hamiltonian cycles in the same graph are symmetric under 40° rotations of the drawing.