Petersen graph

Julius Petersen (1839-1910) was a Danish mathematician. Around 1898 he constructed the graph bearing his name as the smallest counterexample against the claim that a connected bridgeless cubic graph has an edge colouring with three colours. The Petersen graph is also a cage (graph with smallest possible number of vertices given its valency and girth). The Petersen graph is contained in the complement of the Clebsch graph and the Sp(4,2) Generalized Quadrangle and the Hoffman-Singleton graph . Its extended bipartite double is contained in the Gewirtz graph . The Petersen graph has independence number 4 and chromatic number 3. The five independent sets of size 4 are the sets of four pairs on a given symbol. The twenty 3-colorings are found by taking two independent sets of size four (they have one vertex x in common) and the remaining triple (the neighbours of x). The Petersen graph is maximally non-Hamiltonian: there is a Hamiltonian path between any two nonadjacent vertices.