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