In the
mathematicalMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
field of
graph theoryIn mathematics and computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, 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 PetersenJulius Peter Christian Petersen was a Danish mathematician.-Biography:Petersen's interests in mathematics were manifold .His famous paper Die Theorie der regulären graphs was a fundamental contribution to...
, who in 1898 constructed it to be the smallest
bridgelessIn graph theory, a bridge is an edge whose deletion increases the number of connected components . Equivalently, an edge is a bridge if and only if it is not contained in any cycle.A graph is said to be bridgeless if it contains no bridges...
cubic graphIn the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs...
with no three-edge-coloring. Although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in 1886.
Donald KnuthDonald Ervin Knuth is a renowned computer scientist and Professor Emeritus of the Art of Computer Programming at Stanford University....
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."
Constructions
The Petersen graph is the
complementIn graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is to find the complement of a graph, you fill in all the missing edges to get a complete graph, and remove all the...
of the
line graphIn a graph theory, the line graph L of an undirected graph G is another graph L that represents the adjacencies between edges of G...
of . It is also the
Kneser graphIn graph theory, the Kneser graph is the graph whose vertices correspond to the -element subsets of a set of elements, and where two vertices are connected if and only if the two corresponding sets are disjoint...
; this means that you can form the Petersen graph by constructing a vertex for each 2-element subset of a 5-element set, and connecting two vertices by an edge if the corresponding 2-element subsets are disjoint from each other.
Geometrically, the Petersen graph is the graph formed by the vertices and edges of the
hemi-dodecahedronA hemi-dodecahedron is an abstract regular polyhedron, containing half the faces of a regular dodecahedron. It exists on a hemisphere as a real projective plane where opposite points along the boundary are connected....
, that is, a
dodecahedronIn geometry, a dodecahedron is any polyhedron with twelve faces, but usually a regular dodecahedron is meant: a Platonic solid. It is composed of 12 regular pentagonal faces, with three meeting at each vertex, and is represented by the Schläfli symbol {5,3}. It has 20 vertices and 30 edges...
with opposite points, lines and faces identified together.
Embeddings
The Petersen graph is
nonplanarIn graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints....
. Any nonplanar graph has as
minorIn graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. An edge contraction is an operation which removes an edge from a graph while simultaneously merging together the two vertices it used...
s either the
complete graphIn the mathematical field of graph theory, a complete graph is a simple graph in which every pair of distinct vertices is connected by an edge. The complete graph on n vertices has n vertices and n/2 edges, and is denoted by . It is a regular graph of degree . All complete graphs are their own...
, or the
complete bipartite graphIn the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
, but the Petersen graph has both as minors. The minor can be formed by contracting the edges of a perfect matching, for instance the five short edges in the first picture. The minor can be formed by deleting one vertex (for instance the central vertex of the 3-symmetric drawing) and contracting an edge incident to each neighbor of the deleted vertex.
The most common and symmetric plane drawing of the Petersen graph, as a pentagram within a pentagon, has five crossings. However, this is not the best drawing for minimizing crossings; there exists another drawing (shown in the figure) with only two crossings. Thus, the Petersen graph has
crossing numberIn graph theory, the crossing number cr of a graph G is the lowest number of crossings of a planar drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero...
2. On a
torusIn geometry, a torus is a surface of revolution generated by revolving a circle in three dimensional space about an axis coplanar with and not touching the circle. Examples of tori include the surfaces of doughnuts and inner tubes. The solid contained by the surface is known as a toroid...
the Petersen graph can be drawn without edge crossings; it therefore has
orientable genusIn mathematics, genus has a few different, but closely related, meanings:-Orientable surface:The genus of a connected, orientable surface is an integer representing the maximum number of cuttings along closed simple curves without rendering the resultant manifold disconnected. It is equal to the...
1.
The Petersen graph can also be drawn (with crossings) in the plane in such a way that all the edges have equal length. That is, it is a
unit distance graphIn mathematics, and particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one...
.
The simplest
non-orientable surfaceIn mathematics, specifically in topology, a surface is a two-dimensional topological manifold. The most familiar examples are those that arise as the boundaries of solid objects in ordinary three-dimensional Euclidean space R
3 — for example, the surface of a ball...
on which the Petersen graph can be embedded without crossings is the
projective planeIn mathematics, a projective plane has two possible definitions, one of them coming from linear algebra, and another coming from axiomatic and finite geometry. The first definition quickly produces planes that are homogeneous spaces for some of the classical groups, including the real projective...
. This is the embedding given by the
hemi-dodecahedronA hemi-dodecahedron is an abstract regular polyhedron, containing half the faces of a regular dodecahedron. It exists on a hemisphere as a real projective plane where opposite points along the boundary are connected....
construction of the Petersen graph. The projective plane embedding can also be formed from the standard pentagonal drawing of the Petersen graph by placing a
cross-capIn mathematics, a cross-cap is a two-dimensional surface that is topologically equivalent to a Möbius strip. The term 'cross-cap', however, often implies that the surface has been deformed so that its boundary is an ordinary circle....
within the five-point star at the center of the drawing, and routing the star edges through this cross-cap; the resulting drawing has six pentagonal faces. This construction shows that the Petersen graph has
non-orientable genusIn mathematics, genus has a few different, but closely related, meanings:-Orientable surface:The genus of a connected, orientable surface is an integer representing the maximum number of cuttings along closed simple curves without rendering the resultant manifold disconnected. It is equal to the...
1.
Symmetries
The Petersen graph is
strongly regularLet G = be a regular graph with v vertices and degree k. G is said to be strongly regular if there are also integers λ and μ such that:* Every two adjacent vertices have λ common neighbours....
. It is also
symmetricIn the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of linked vertices u1—v1 and u2—v2 of G, there is an automorphismsuch that...
, meaning that it is
edge transitiveIn the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is anautomorphism of G that maps e1 to e2....
and
vertex transitiveIn the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphismsuch that...
. It is one of only 13 cubic
distance-regular graphIn mathematics, a distance-regular graph is a regular graph such that for any two vertices v and w at distance i the number of vertices adjacent to w and at distance j from v is the same. Every distance-transitive graph is distance regular...
s.
The
automorphism groupIn the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity....
of the Petersen graph is the
symmetric groupIn mathematics, the symmetric group on a set is the group consisting of all automorphisms of the set with function composition as the group operation....
; the action of on the Petersen graph follows from its construction as a
Kneser graphIn graph theory, the Kneser graph is the graph whose vertices correspond to the -element subsets of a set of elements, and where two vertices are connected if and only if the two corresponding sets are disjoint...
. Every
homomorphismIn the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps adjacent vertices to adjacent vertices.-Definition:...
of the Petersen graph to itself that doesn't identify adjacent vertices is an automorphism. As shown in the figures, the drawings of the Petersen graph may exhibit five-way or three-way symmetry, but it is not possible to draw the Petersen graph in the plane in such a way that the drawing exhibits the full symmetry group of the graph.
Despite its high degree of symmetry, the Petersen graph is not a
Cayley graphIn mathematics, a Cayley graph, also known as a Cayley colour graph, is a graph that encodes the structure of a discrete group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...
. It is the smallest vertex-transitive graph that is not a Cayley graph.
Hamiltonian paths and cycles
The Petersen graph has a
Hamiltonian pathIn the mathematical field of graph theory, a Hamiltonian path , is a path in an undirected graph which visits each vertex exactly once. A Hamiltonian cycle is a cycle in an undirected graph which visits each vertex exactly once and also returns to the starting vertex...
but no Hamiltonian cycle. It is the smallest bridgeless cubic graph with no Hamiltonian cycle. It is
hypohamiltonianIn the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.-History:...
, meaning that although it has no Hamiltonian cycle, deleting any vertex makes it Hamiltonian, and is the smallest hypohamiltonian graph.
As a finite connected vertex-transitive graph whose don't contains a Hamiltonian cycle, the Petersen graph is a counterexample to a variant of the
Lovász conjectureIn graph theory, the Lovász conjecture is a classical problem on Hamiltonian paths in graphs. It says:The original article of Lovász stated the result in the opposite, butthis version became standard...
, but the canonical formulation of the conjecture asks for an Hamiltonian path and is verified by the Petersen graph.
Only five examples of vertex-transitive graph with no Hamiltonian cycles are known : the
complete graphIn the mathematical field of graph theory, a complete graph is a simple graph in which every pair of distinct vertices is connected by an edge. The complete graph on n vertices has n vertices and n/2 edges, and is denoted by . It is a regular graph of degree . All complete graphs are their own...
K2, the Petersen graph, the
Coxeter graphIn the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. All the cubic distance-regular graphs are known. The Coxeter graph is one of the 13 such graphs....
and two graphs derived from the Petersen and Coxeter graphs by replacing each vertex with a triangle. If
G is a 2-connected,
r-regular graph with at most 3
r + 1 vertices, then
G is Hamiltonian or
G is the Petersen graph.
To see that the Petersen graph has no Hamiltonian cycle
C, we describe the ten-vertex
3-regular graphsIn graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i.e. every vertex has the same degree or valency...
that do have a Hamiltonian cycle and show that none of them is the Petersen graph, by finding a cycle in each of them that is shorter than any cycle in the Petersen graph. Any ten-vertex Hamiltonian 3-regular graph consists of a ten-vertex cycle
C plus five chords. If any chord connects two vertices at distance two or three along
C from each other, the graph has a 3-cycle or 4-cycle, and therefore cannot be the Petersen graph. If two chords connect opposite vertices of
C to vertices at distance four along
C, there is again a 4-cycle. The only remaining case is a
Möbius ladderIn the mathematical area of graph theory, the Möbius ladder Mn is a cubic circulant graph with an even number n of vertices, formed from an n-cycle by adding edges connecting opposite pairs of vertices in the cycle...
formed by connecting each pair of opposite vertices by a chord, which again has a 4-cycle. Since the Petersen graph has girth five, it cannot be formed in this way and has no Hamiltonian cycle.
Coloring
The Petersen graph has chromatic number 3, meaning that its vertices can be
coloredIn graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
with three colors — but not with two — such that no edge connects vertices of the same color.
The Petersen graph has chromatic index 4; coloring the edges requires four colors. A proof of this requires checking four cases to demonstrate that no 3-edge-coloring exists. As a connected bridgeless cubic graph with chromatic index four, the Petersen graph is a
snarkIn the mathematical field of graph theory, a snark is a connected, bridgeless cubic graph with chromatic index equal to 4. In other words, it is a graph in which every vertex has three neighbors, and the edges cannot be colored by three colors without two edges of the same color meeting at a point...
. It is the smallest possible snark, and was the only known snark from 1898 until 1946. The
snark theoremIn the mathematical field of graph theory, a snark is a connected, bridgeless cubic graph with chromatic index equal to 4. In other words, it is a graph in which every vertex has three neighbors, and the edges cannot be colored by three colors without two edges of the same color meeting at a point...
, a result conjectured by
W. T. TutteWilliam Thomas Tutte, OC was a British, later Canadian, codebreaker and mathematician. During World War II he broke a major German code system, which had a significant impact on the Allied invasion of Europe...
and announced in 2001 by Robertson, Sanders, Seymour, and Thomas, states that every snark has the Petersen graph as a
minorIn graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. An edge contraction is an operation which removes an edge from a graph while simultaneously merging together the two vertices it used...
.
Additionally, the graph has fractional chromatic index 3, proving that the difference between the chromatic index and fractional chromatic index can be as large as 1. The long-standing Goldberg-Seymour Conjecture proposes that this is the largest gap possible.
The
Thue numberIn the mathematical area of graph theory, the Thue number of a graph is a variation of the chromatic index, defined by Alon et al. and named by them after mathematician Axel Thue, who studied the squarefree words used to define this number.Alon et al...
(a variant of the chromatic index) of the Petersen graph is 5.
Other properties
The Petersen graph:
- is 3-connected and hence 3-edge-connected and bridgeless. See the glossary.
- has independence number 4 and is 3-partite. See the glossary.
- is cubic
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs...
, has domination number 3, and has a perfect matching and a 2-factor. See the glossary.
- has radius 2 and diameter 2. It is the largest cubic graph with diameter 2.
- has graph spectrum
In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of its adjacency matrix or Laplacian matrix....
−2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
- is the smallest cubic graph of girth 5. (It is the unique -cage
In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.Formally, an -graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle has length exactly g. It is known that an -graph exists...
. In fact, since it has only 10 vertices, it is the unique -Moore graphIn graph theory, a Moore graph is a regular graph of degree d and diameter k whose number of vertices equals the upper boundAn equivalent definition of a Moore graph is that it is a graph of diameter k with girth 2k + 1. Moore graphs were named by after Edward F...
.)
- has 2000 spanning tree
In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree composed of all the vertices and some of the edges of G. Informally, a spanning tree of G is a selection of edges of G that form a tree spanning every vertex...
s, the most of any 10-vertex cubic graph.
- has chromatic polynomial
The chromatic polynomial is a polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to attack the four color problem. It was generalised to the Tutte...
- has characteristic polynomial
Generalized Petersen graphs
In 1950 H. S. M. Coxeter introduced a family of graphs generalizing the Petersen graph. These graphs are now called
generalized Petersen graphs, a name given to them in 1969 by Mark Watkins. In Watkins' notation,
G(
n,
k) is a graph
with vertex set
- {u0, u1, ..., un−1, v0, v1, ..., vn−1}
and edge set
- {ui ui+1, ui vi, vi vi+k: i = 0,...,n − 1}
where subscripts are to be read modulo
n and
k <
n/2. Coxeter's notation for the same graph would be {
n}+{
n/k}.
The Petersen graph itself is
G(5,2) or {5}+{5/2}.
This family of graphs possesses a number of interesting properties. For example,
- G(n,k) is vertex-transitive if and only if n = 10 and k =2 or if k2 ≡ ±1 (mod n).
- It is edge-transitive only in the following seven cases: (n,k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5). These seven graphs are therefore the only symmetric
In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of linked vertices u1—v1 and u2—v2 of G, there is an automorphismsuch that...
generalized Petersen graphs.
- It is bipartite
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
if and only if n is even and k is odd.
- It is a Cayley graph
In mathematics, a Cayley graph, also known as a Cayley colour graph, is a graph that encodes the structure of a discrete group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...
if and only if k2 ≡ 1 (mod n).
- It is hypohamiltonian
In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.-History:...
when n is congruent to 5 modulo 6 and k is 2, n−2, (n+1)/2, or (n−1)/2 (all four of these choice of k lead to isomorphic graphs). It is also non-Hamiltonian when n is divisible by four, at least equal to 8, and k is n/2. In all other cases it has a Hamiltonian cycle .
Among the generalized Petersen graphs are the
n-prism ,
the
Dürer graphIn the mathematical field of graph theory, the Dürer graph is an undirected graph with 12 vertices and 18 edges. It is named after Albrecht Dürer, whose 1514 engraving Melencolia I includes a depiction of Dürer's solid, a polyhedron having the Dürer graph as its skeleton.-Dürer's solid:Dürer's...
, the Möbius-Kantor graph
, the
dodecahedronIn geometry, a dodecahedron is any polyhedron with twelve faces, but usually a regular dodecahedron is meant: a Platonic solid. It is composed of 12 regular pentagonal faces, with three meeting at each vertex, and is represented by the Schläfli symbol {5,3}. It has 20 vertices and 30 edges...
, the
Desargues graphIn the mathematical field of graph theory, the Desargues graph is a distance-transitive cubic graph with 20 vertices and 30 edges. It arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in...
and the
Nauru graphIn the mathematical field of graph theory, the Nauru graph is a symmetric bipartite cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru....
.
The Petersen graph itself is the only generalized Petersen graph that is not 3-
edge-colorableIn graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green...
.
Petersen family
The
Petersen family consists of the seven graphs that can be formed from the Petersen graph by zero or more applications of Δ-Y or Y-Δ transforms. A graph is intrinsically linked in three dimensional real space if and only if it contains one of these graphs as a minor.