Petersen graph

Petersen graph --- граф Петерсена.

A generalized Petersen graph [math]\displaystyle{ P(n,m) }[/math], [math]\displaystyle{ 1 \leq m \leq \frac{n}{2} }[/math], consists of an outer [math]\displaystyle{ n }[/math]-cycle [math]\displaystyle{ y_{1},Y_{2}, \ldots, y_{n} }[/math], a set of [math]\displaystyle{ n }[/math] spokes [math]\displaystyle{ y_{i}x_{i}, \; 1 \leq i \leq n }[/math], and [math]\displaystyle{ n }[/math] inner edges [math]\displaystyle{ x_{i}x_{i+m} }[/math], [math]\displaystyle{ 1 \leq i \leq n }[/math], with indices taken modulo [math]\displaystyle{ n }[/math].

The standard Petersen graph is the instance [math]\displaystyle{ P(5,2) }[/math]. It is possible to form the Petersen graph by constructing a vertex for each 2-element subset of a 5-element set, and connecting two vertices by an edge if the corresponding 2-element subsets are disjoint from each other.

The Petersen graph is a small graph that serves as a useful example and counterexample for many problems in graph theory. It is named for Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no edge 3-coloring.