Petersen graph

The Petersen graph is a 10-vertex, 15-edge graph with girth 5. It is nonplanar and is the smallest bridgeless cubic graph that has no 3-edge-coloring.

Graph automorphism: A graph automorphism is a permutation of vertices that preserves adjacency. The Petersen graph has a large automorphism group that makes its vertices and edges structurally equivalent.
Graph (discrete mathematics): A graph is a mathematical structure consisting of vertices joined by edges. The Petersen graph is a finite graph with ten vertices and fifteen edges.
Julius Petersen: Julius Petersen was a Danish mathematician whose work included influential contributions to graph theory. The graph bears Petersen’s name after he studied it in connection with a theorem on cubic graphs.
Tait's conjecture: Tait's conjecture states that every bridgeless cubic planar graph has a 3-edge-coloring. The Petersen graph is nonplanar, so it does not refute the conjecture’s planar condition.
Complete graph: A complete graph contains an edge between every pair of distinct vertices. Unlike the sparse Petersen graph, a complete graph maximizes adjacency among its vertices.
Vertex-transitive graph: A vertex-transitive graph has an automorphism mapping any vertex to any other vertex. Every Petersen graph vertex occupies the same position under its symmetries.
Cubic graph: A cubic graph is a graph in which every vertex has degree three. Each Petersen graph vertex is incident to exactly three edges.
Alfred Kempe: Alfred Kempe was a British mathematician known for work on graph coloring and the four-color problem. Petersen introduced the graph while examining an argument related to Kempe’s attempted proof.
Snark (graph theory): A snark is a bridgeless cubic graph with chromatic index four, subject to common additional restrictions. The Petersen graph is the smallest and best-known example of a snark.
Dodecahedral graph: The dodecahedral graph is the planar 20-vertex graph formed by the edges of a dodecahedron. It is another cubic graph of girth five, but unlike the Petersen graph it is planar.

Linked from 6 pages