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 Graph: Constructions, 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) ...

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

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

**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)