Petersen graph

Petersen graph
The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes.
Named after	Julius Petersen
Vertices	10
Edges	15
Radius	2
Diameter	2
Girth	5
Automorphisms	120 (S5)
Chromatic number	3
Chromatic index	4
Fractional chromatic index	3
Genus	1
Properties	Cubic Strongly regular Distance-transitive Snark

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

Although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in a paper by A. B. Kempe (1886). Kempe observed that its vertices can represent the ten lines of the Desargues configuration, and its edges represent pairs of lines that do not meet at one of the ten points of the configuration.

Donald Knuth states that the Petersen graph is "a remarkable configuration that serves as a counterexample to many optimistic predictions about what might be true for graphs in general."

The Petersen graph also makes an appearance in tropical geometry. The cone over the Petersen graph is naturally identified with the moduli space of five-pointed rational tropical curves.

The Petersen graph is the complement of the line graph of ${\displaystyle K_{5}}$. It is also the Kneser graph ${\displaystyle KG_{5,2}}$; this means that it has one vertex for each 2-element subset of a 5-element set, and two vertices are connected by an edge if and only if the corresponding 2-element subsets are disjoint from each other. As a Kneser graph of the form ${\displaystyle KG_{2n-1,n-1}}$ it is an example of an odd graph.