Generalized Petersen graph

G(n, k) is isomorphic to G(n, l) if and only if k=l or kl ≡ ±1 (mod n).[10]

The girth of G(n, k) is at least 3 and at most 8, in particular:[11]

${\displaystyle g(G(n,k))\leq \min \left\{8,k+3,{\frac {n}{\gcd(n,k)}}\right\}.}$

A table with exact girth values:

Condition	Girth
${\displaystyle n=3k}$	3
${\displaystyle n=4k}$	4
${\displaystyle k=1}$
${\displaystyle n=5k}$	5
${\displaystyle n=5k/2}$
${\displaystyle k=2}$
${\displaystyle n=6k}$	6
${\displaystyle k=3}$
${\displaystyle n=2k+2}$
${\displaystyle n=7k}$	7
${\displaystyle n=7k/2}$
${\displaystyle n=7k/3}$
${\displaystyle k=4}$
${\displaystyle n=2k+3}$
${\displaystyle n=3k\pm 2}$
otherwise	8

Being regular, according to Brooks' theorem their chromatic number can not be larger than their degree. Generalized Petersen graphs are cubic, so their chromatic number can be either 2 or 3. More exactly:

${\displaystyle \chi (G(n,k))={\begin{cases}2&2\mid n\land 2\nmid k\\3&2\nmid n\lor 2\mid k\\\end{cases}}}$

Where ${\displaystyle \land }$ denotes the logical AND, while ${\displaystyle \lor }$ the logical OR. For example, the chromatic number of ${\displaystyle G(5,2)}$ is 3.

• 
  A 3-coloring of the Petersen graph or ${\displaystyle G(5,2)}$
• 
  A 2-coloring of the Desargues graph or ${\displaystyle G(10,3)}$
• 
  A 3-coloring of the Dürer graph or ${\displaystyle G(6,2)}$

Petersen graph, being a snark, has a chromatic index of 4. All other generalized Petersen graph has chromatic index 3.[12]

The generalized Petersen graph G(9, 2) is one of the few graphs known to have only one 3-edge-coloring.[13]

• 
  A 4-edge-coloring of the Petersen graph or ${\displaystyle G(5,2)}$
• 
  A 3-edge-coloring of the Dürer graph or ${\displaystyle G(6,2)}$
• 
  A 3-edge-coloring of the dodecahedron or ${\displaystyle G(10,2)}$
• 
  A 3-edge-coloring of the Desargues graph or ${\displaystyle G(10,3)}$
• 
  A 3-edge-coloring of the Nauru graph or ${\displaystyle G(12,5)}$

The Petersen graph itself is the only generalized Petersen graph that is not 3-edge-colorable.[14]

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

Admissible matrices

	G(n, 2)	G(n, 3)
${\displaystyle {\begin{bmatrix}2&1\\1&2\end{bmatrix}}}$	All graphs	All graphs
${\displaystyle {\begin{bmatrix}2&1\\2&1\end{bmatrix}}}$	Just G(3m, 2)	No graphs
${\displaystyle {\begin{bmatrix}1&2\\2&1\end{bmatrix}}}$	No graphs	Just G(2m,3)
${\displaystyle {\begin{bmatrix}0&3\\1&2\end{bmatrix}}}$	No graphs	Just G(4m,3)
${\displaystyle {\begin{bmatrix}0&3\\2&1\end{bmatrix}}}$	Just G(5m,2)	Just G(5m,3)
${\displaystyle {\begin{bmatrix}0&3\\3&0\end{bmatrix}}}$	No graphs	Just G(2m,3)