The Petersen graph is an undirected graph with ten vertices and fifteen edges, most commonly drawn as an outer pentagon and an inner pentagram connected by five spokes. Julius Petersen constructed it in 1898 as the smallest bridgeless cubic graph that cannot be properly edge-colored with only three colors, disproving a conjectured generalization of an earlier result by Alfred Kempe. Because it combines high symmetry with a habit of failing plausible-sounding conjectures, the Petersen graph has become one of the standard counterexamples in graph theory, described by Donald Knuth as a configuration that serves as a counterexample to many optimistic predictions about what might be true for graphs in general.
Facts
FAQs
Was the Petersen graph first described by Julius Petersen?
Petersen introduced it in 1898 as a counterexample; Kempe described it twelve years earlier.
Not quite. Wolfram MathWorld says the graph was introduced by Petersen in 1898 as a counterexample to an edge coloring problem, but that it was described twelve years earlier by Kempe in 1886 as the graph whose vertices correspond to the points of the Desargues configuration and whose edges join pairs of points that do not lie on lines that are part of the configuration.
Connections
Attributed To
Source Petersen Graph (Wikipedia)
In Branch
Source Petersen Graph (Wikipedia)
Is Kind Of Object
Sources
1. Petersen Graph (Wikipedia)
Wikimedia FoundationLead section
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges.
- In Branch: Graph Theory
Attributed To: Julius Petersen, Lead
The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.