
In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a cubic graph is a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
in which all
vertices have
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathemati ...
three. In other words, a cubic graph is a 3-
regular graph
In 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. A regular directed graph must also satisfy the stronger condition that the indegree and outdegre ...
. Cubic graphs are also called trivalent graphs.
A bicubic graph is a cubic
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...
.
Symmetry
In 1932,
Ronald M. Foster began collecting examples of cubic
symmetric graphs, forming the start of the
Foster census.
[.] Many well-known individual graphs are cubic and symmetric, including the
utility graph
As a topic of economics, utility is used to model worth or value. Its usage has evolved significantly over time. The term was introduced initially as a measure of pleasure or happiness as part of the theory of utilitarianism by moral philosophe ...
, the
Petersen graph
In the mathematics, mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertex (graph theory), vertices and 15 edge (graph theory), edges. It is a small graph that serves as a useful example and counterexample for ...
, the
Heawood graph, the
Möbius–Kantor graph, the
Pappus graph, the
Desargues graph, the
Nauru graph, the
Coxeter graph, the
Tutte–Coxeter graph, the
Dyck graph, the
Foster graph and the
Biggs–Smith graph.
W. T. Tutte classified the symmetric cubic graphs by the smallest integer number ''s'' such that each two oriented paths of length ''s'' can be mapped to each other by exactly one symmetry of the graph. He showed that ''s'' is at most 5, and provided examples of graphs with each possible value of ''s'' from 1 to 5.
Semi-symmetric cubic graphs include the
Gray graph (the smallest semi-symmetric cubic graph), the
Ljubljana graph, and the
Tutte 12-cage.
The
Frucht graph
In the mathematical field of graph theory, the Frucht graph is a cubic graph with 12 vertices, 18 edges, and no nontrivial symmetries. It was first described by Robert Frucht in 1939.
The Frucht graph is a pancyclic, Halin graph with chromatic ...
is one of the five smallest cubic graphs without any symmetries: it possesses only a single
graph automorphism, the identity automorphism.
Coloring and independent sets
According to
Brooks' theorem every connected cubic graph other than the
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...
''K''
4 has a
vertex coloring with at most three colors. Therefore, every connected cubic graph other than ''K''
4 has an
independent set of at least ''n''/3 vertices, where ''n'' is the number of vertices in the graph: for instance, the largest color class in a 3-coloring has at least this many vertices.
According to
Vizing's theorem every cubic graph needs either three or four colors for an
edge coloring
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...
. A 3-edge-coloring is known as a Tait coloring, and forms a partition of the edges of the graph into three
perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
s. By
Kőnig's line coloring theorem every bicubic graph has a Tait coloring.
The bridgeless cubic graphs that do not have a Tait coloring are known as
snarks. They include the
Petersen graph
In the mathematics, mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertex (graph theory), vertices and 15 edge (graph theory), edges. It is a small graph that serves as a useful example and counterexample for ...
,
Tietze's graph, the
Blanuša snarks, the
flower snark, the
double-star snark
In the mathematical field of graph theory, the double-star snark is a snark with 30 vertices and 45 edges.
In 1975, Rufus Isaacs introduced two infinite families of snarks—the flower snark and the BDS snark, a family that includes the two B ...
, the
Szekeres snark
In the mathematical field of graph theory, the Szekeres snark is a snark with 50 vertices and 75 edges. It was the fifth known snark, discovered by George Szekeres in 1973.
As a snark, the Szekeres graph is a connected, bridgeless cubic graph wi ...
and the
Watkins snark
In the mathematical field of graph theory, the Watkins snark is a snark with 50 vertices and 75 edges. It was discovered by John J. Watkins in 1989.
As a snark, the Watkins graph is a connected, bridgeless cubic graph with chromatic index equal ...
. There is an infinite number of distinct snarks.
Topology and geometry
Cubic graphs arise naturally in
topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ho ...
in several ways. For example, if one considers a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
to be a 1-dimensional
CW complex
A CW complex (also called cellular complex or cell complex) is a kind of a topological space that is particularly important in algebraic topology. It was introduced by J. H. C. Whitehead (open access) to meet the needs of homotopy theory. This cla ...
, cubic graphs are ''
generic'' in that most 1-cell attaching maps are disjoint from the 0-skeleton of the graph. Cubic graphs are also formed as the graphs of
simple polyhedra in three dimensions, polyhedra such as the
regular dodecahedron with the property that three faces meet at every vertex.

An arbitrary
graph embedding
In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs ( homeomorphic images of ,1/math> ...
on a two-dimensional surface may be represented as a cubic graph structure known as a
graph-encoded map. In this structure, each vertex of a cubic graph represents a
flag
A flag is a piece of fabric (most often rectangular or quadrilateral) with a distinctive design and colours. It is used as a symbol, a signalling device, or for decoration. The term ''flag'' is also used to refer to the graphic design emp ...
of the embedding, a mutually incident triple of a vertex, edge, and face of the surface. The three neighbors of each flag are the three flags that may be obtained from it by changing one of the members of this mutually incident triple and leaving the other two members unchanged.
Hamiltonicity
There has been much research on
Hamiltonicity of cubic graphs. In 1880,
P.G. Tait conjectured that every cubic
polyhedral graph has a
Hamiltonian circuit.
William Thomas Tutte
William Thomas Tutte Order of Canada, OC Royal Society, FRS Royal Society of Canada, FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian cryptanalysis, codebreaker and mathematician. During the Second World War, he made a brilliant a ...
provided a counter-example to
Tait's conjecture, the 46-vertex
Tutte graph, in 1946. In 1971, Tutte conjectured that all bicubic graphs are Hamiltonian. However, Joseph Horton provided a counterexample on 96 vertices, the
Horton graph
In the mathematical field of graph theory, the Horton graph or Horton 96-graph is a 3- regular graph with 96 vertices and 144 edges discovered by Joseph Horton. Published by Bondy and Murty in 1976, it provides a counterexample to the Tutte conjec ...
.
[Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.] Later,
Mark Ellingham
Mark Norman Ellingham is a professor of mathematics at Vanderbilt University whose research concerns graph theory. With Joseph D. Horton, he is the discoverer and namesake of the Ellingham–Horton graphs, two cubic 3-vertex-connected bipartite g ...
constructed two more counterexamples: the
Ellingham–Horton graph
In the mathematical field of graph theory, the Ellingham–Horton graphs are two 3- regular graphs on 54 and 78 vertices: the Ellingham–Horton 54-graph and the Ellingham–Horton 78-graph. They are named after Joseph D. Horton and Mark N. Elli ...
s.
[Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.][.] Barnette's conjecture
Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that ev ...
, a still-open combination of Tait's and Tutte's conjecture, states that every bicubic polyhedral graph is Hamiltonian. When a cubic graph is Hamiltonian,
LCF notation allows it to be represented concisely.
If a cubic graph is chosen
uniformly at random among all ''n''-vertex cubic graphs, then it is very likely to be Hamiltonian: the proportion of the ''n''-vertex cubic graphs that are Hamiltonian tends to one in the limit as ''n'' goes to infinity.
David Eppstein conjectured that every ''n''-vertex cubic graph has at most 2
''n''/3 (approximately 1.260
''n'') distinct Hamiltonian cycles, and provided examples of cubic graphs with that many cycles. The best proven estimate for the number of distinct Hamiltonian cycles is
.
Other properties
The
pathwidth of any ''n''-vertex cubic graph is at most ''n''/6. The best known lower bound on the pathwidth of cubic graphs is 0.082''n''. It is not known how to reduce this gap between this
lower bound and the ''n''/6 upper bound.
[.]
It follows from the
handshaking lemma, proven by
Leonhard Euler
Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...
in 1736 as part of the first paper on graph theory, that every cubic graph has an even number of vertices.
Petersen's theorem states that every cubic
bridgeless graph has a
perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
.
[.]
Lovász Lovász ():
* Lázár Lovász (born 1942), a Hungarian athlete who competed in hammer throw
* László Lovász (born 1948, Budapest), a mathematician, best known for his work in combinatorics,
**Lovász conjecture (1970)
** Erdős–Faber–Lovász ...
and
Plummer
Plummer may refer to:
Places Communities
*Plummer, Idaho, United States
*Plummer, Indiana, United States
*Plummer, Minnesota, United States
*Plummer Additional, Ontario, Canada
Buildings
*Plummer Building, Rochester, Minnesota, United States
* P ...
conjectured that every cubic bridgeless graph has an exponential number of perfect matchings. The conjecture was recently proved, showing that every cubic bridgeless graph with ''n'' vertices has at least 2
n/3656 perfect matchings.
[.]
Algorithms and complexity
Several researchers have studied the complexity of
exponential time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
algorithms restricted to cubic graphs. For instance, by applying
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
I ...
to a
path decomposition of the graph, Fomin and Høie showed how to find their
maximum independent sets in time 2
''n''/6 + o(''n'').
The
travelling salesman problem
The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
in cubic graphs can be solved in time O(1.2312
''n'') and polynomial space.
[.]
Several important graph optimization problems are
APX hard, meaning that, although they have
approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...
s whose
approximation ratio
An approximation is anything that is intentionally similar but not exactly equal to something else.
Etymology and usage
The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix '' ...
is bounded by a constant, they do not have
polynomial time approximation schemes whose approximation ratio tends to 1 unless
P=NP. These include the problems of finding a minimum
vertex cover
In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.
In computer science, the problem of finding a minimum vertex cover is a classical optimiza ...
,
maximum independent set, minimum
dominating set
In graph theory, a dominating set for a graph is a subset of its vertices, such that any vertex of is either in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for .
The dominating set ...
, and
maximum cut.
The
crossing number (the minimum number of edges which cross in any
graph drawing) of a cubic graph is also
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
for cubic graphs but may be approximated.
[.]
The
Travelling Salesman Problem
The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
on cubic graphs has been proven to be
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
to approximate to within any factor less than 1153/1152.
[.]
See also
*
Table of simple cubic graphs
References
External links
*
*
*{{mathworld, urlname=CubicGraph, title=Cubic Graph
Graph families
Regular graphs