Petersen Graph

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 for 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).

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."

Read more about Petersen GraphConstructions, Embeddings, Symmetries, Hamiltonian Paths and Cycles, Coloring, Other Properties, Petersen Coloring Conjecture, Related Graphs

Other articles related to "petersen graph, petersen graphs, graph":

Petersen Graph - Related Graphs
... The generalized Petersen graph G(n,k) is formed by connecting the vertices of a regular n-gon to the corresponding vertices of a star polygon with Schläfli symbol {n/k} ... For instance, in this notation, the Petersen graph is G(5,2) it can be formed by connecting corresponding vertices of a pentagon and five-point star, and the edges in the star ... The generalized Petersen graphs also include the n-prism G(n,1) the Dürer graph G(6,2), the Möbius-Kantor graph G(8,3), the dodecahedron G(10,2), the Desargues graph G(10,3) and the Nauru graph G(12,5) ...
Tietze's Graph
... In the mathematical field of graph theory, Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges, formed by applying a Y-Δ transform to ... Tietze's graph has chromatic number 3, chromatic index 4, girth 3 and diameter 3 ... size 3 and one of size 6 on vertices, and thus this graph is not vertex-transitive ...
Desargues Graph - Algebraic Properties
... The Desargues graph is a symmetric graph it has symmetries that take any vertex to any other vertex and any edge to any other edge ... of the symmetry group in terms of the constructions of the Desargues graph the symmetric group on five points is the symmetry group of the Desargues configuration, and the order-2 subgroup swaps the roles of the ... Alternatively, in terms of the bipartite Kneser graph, the symmetric group on five points acts separately on the two-element and three-element subsets of the five points, and ...
Hemi-dodecahedron - Petersen Graph
... From the point of view of graph theory this is an embedding of Petersen graph on a real projective plane ... With this embedding, the dual graph is K6 (the complete graph with 6 vertices) --- see hemi-icosahedron ...

Famous quotes containing the word graph:

    When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.
    Marshall McLuhan (1911–1980)