Cubic graph
Encyclopedia
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.
A bicubic graph is a cubic bipartite graph
.
began collecting examples of cubic symmetric graph
s, forming the start of the Foster census. Many well-known individual graphs are cubic and symmetric, including the utility graph, the Petersen graph
, 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 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
is one of the two smallest cubic graphs without any symmetries: it possesses only a single graph automorphism
, the identity automorphism.
K4 can be colored
with at most three colors. Therefore, every cubic graph other than K4 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. A 3-edge-coloring is known as a Tait coloring, and forms a partition of the edges of the graph into three perfect matchings. 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
, Tietze's graph
, the Blanuša snarks
, the flower snark
, the double-star snark
, the Szekeres snark
and the Watkins snark
. There is an infinite number of distinct snarks.
in several ways. For example, if one considers a graph
to be a 1-dimensional CW complex
, 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
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 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.
conjectured that every cubic polyhedral graph
has a Hamiltonian circuit. William Thomas Tutte 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
. Later, Mark Ellingham constructed two more counterexamples : the Ellingham-Horton graph
s. Barnette's conjecture
, 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 2n/3 (approximately 1.260n) distinct Hamiltonian cycles, and provided examples of cubic graphs with that many cycles. The best upper bound that has been proven on the number of distinct Hamiltonian cycles is 1.276n.
It follows from the handshaking lemma
, proven by Leonhard Euler
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.
Lovász
and Plummer 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 2n/3656 perfect matchings.
to a path decomposition
of the graph, Fomin and Høie showed how to find their maximum independent sets in time O(2n/6 + o(n)). The travelling salesman problem
can be solved in cubic graphs in time O(1.251n).
Several important graph optimization problems are APX hard
, meaning that, although they have approximation algorithm
s whose approximation ratio 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
, maximum independent set, minimum 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
for cubic graphs but may be approximated.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In 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...
, a cubic graph is a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
in which all vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
have degree
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
three. In other words a cubic graph is a 3-regular graph
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 outdegree of each vertex are equal to each other...
. Cubic graphs are also called trivalent graphs.
A bicubic graph is a cubic bipartite graph
Bipartite graph
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...
.
Symmetry
In 1932, Ronald M. FosterR. M. Foster
Ronald Martin Foster , was a Bell Labs mathematician whose work was of significance regarding electronic filters for use on telephone lines...
began collecting examples of cubic symmetric graph
Symmetric graph
In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphismsuch that...
s, forming the start of the Foster census. Many well-known individual graphs are cubic and symmetric, including the utility graph, the Petersen graph
Petersen graph
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...
, the Heawood graph
Heawood graph
In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.-Combinatorial properties:...
, the Möbius–Kantor graph
Möbius–Kantor graph
In the mathematical field of graph theory, the Möbius–Kantor graph is a symmetric bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor...
, the Pappus graph
Pappus graph
In the mathematical field of graph theory, the Pappus graph is a 3-regular undirected graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration. It is named after Pappus of Alexandria, an ancient Greek mathematician who is believed to have discovered the "hexagon...
, the Desargues graph
Desargues graph
In the mathematical field of graph theory, the Desargues graph is a distance-transitive cubic graph with 20 vertices and 30 edges. It is named after Gérard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial...
, the Nauru graph
Nauru graph
In 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 Coxeter graph
Coxeter graph
In 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....
, the Tutte–Coxeter graph, the Dyck graph
Dyck graph
In the mathematical field of graph theory, the Dyck graph is a 3-regular graph with 32 vertices and 48 edges, named after Walther von Dyck.It is Hamiltonian with 120 distinct Hamiltonian cycles. It has chromatic number 2, chromatic index 3, radius 5, diameter 5 and girth 6...
, the Foster graph
Foster graph
In the mathematical field of graph theory, the Foster graph is a 3-regular graph with 90 vertices and 135 edges.The Foster graph is Hamiltonian and has chromatic number 2, chromatic index 3, radius 8, diameter 8 and girth 10. It is also a 3-vertex-connected and 3-edge-connected graph.All the cubic...
and the Biggs-Smith graph. W. T. Tutte
W. T. Tutte
William Thomas Tutte, OC, FRS, known as Bill Tutte, was a British, later Canadian, codebreaker and mathematician. During World War II he made a brilliant and fundamental advance in Cryptanalysis of the Lorenz cipher, a major German code system, which had a significant impact on the Allied...
classified the symmetric cubic graphs by the smallest integer number s such 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
Semi-symmetric graph
In the mathematical field of graph theory, a semi-symmetric graph is an undirected graph that is edge-transitive and regular, but not vertex-transitive....
cubic graphs include the Gray graph
Gray graph
In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discovered by Marion C. Gray in 1932 , then discovered independently by Bouwer 1968 in reply to a question...
(the smallest semi-symmetric cubic graph), the Ljubljana graph
Ljubljana graph
In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges.It is a cubic graph with diameter 8, radius 7, chromatic number 2 and chromatic index 3. Its girth is 10 and there are exactly 168 cycles of length 10 in it...
, and the Tutte 12-cage
Tutte 12-cage
In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges named after W. T. Tutte....
.
The Frucht graph
Frucht graph
In the mathematical field of graph theory, the Frucht graph is a 3-regular graph with 12 vertices, 18 edges, and no nontrivial symmetries. It was first described by Robert Frucht in 1939....
is one of the two smallest cubic graphs without any symmetries: it possesses only a single graph automorphism
Graph automorphism
In 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....
, the identity automorphism.
Coloring and independent sets
According to Brooks' theorem every cubic graph other than the complete graphComplete 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.-Properties:...
K4 can be colored
Graph coloring
In 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 at most three colors. Therefore, every cubic graph other than K4 has an independent set
Independent set
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
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. A 3-edge-coloring is known as a Tait coloring, and forms a partition of the edges of the graph into three perfect matchings. By König's line coloring theorem
König's theorem (graph theory)
In the mathematical area of graph theory, König's theorem, proved by Dénes Kőnig in 1931, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs...
every bicubic graph has a Tait coloring.
The bridgeless cubic graphs that do not have a Tait coloring are known as snarks
Snark (graph theory)
In 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 only three colors without two edges of the same color meeting at a...
. They include the Petersen graph
Petersen graph
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...
, Tietze's graph
Tietze's graph
In the mathematical field of graph theory, the Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges, formed by applying a Y-Δ transform to the Petersen graph and thereby replacing one of its vertices by a triangle....
, the Blanuša snarks
Blanuša snarks
In the mathematical field of graph theory, the Blanuša snarks are two 3-regular graphs with 18 vertices and 27 edges. They were discovered by Croatian mathematician Danilo Blanuša in 1946 and are named after him. When discovered, only one snark was known—the Petersen graph.As snarks, the Blanuša...
, the flower snark
Flower snark
In the mathematical field of graph theory, the flower snarks form an infinite family of snarks introduced by Rufus Isaacs in 1975.As snarks, the flower snarks are a connected, bridgeless cubic graphs with chromatic index equal to 4...
, the double-star snark
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 Blanuša snarks, the Descartes snark and the Szekeres snark...
, the Szekeres snark
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....
and the Watkins snark
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 to 4...
. There is an infinite number of distinct snarks.
Topology and geometry
Cubic graphs arise naturally in topologyTopology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
in several ways. For example, if one considers a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
to be a 1-dimensional CW complex
CW complex
In topology, a CW complex is a type of topological space introduced by J. H. C. Whitehead to meet the needs of homotopy theory. This class of spaces is broader and has some better categorical properties than simplicial complexes, but still retains a combinatorial naturethat allows for...
, 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
Polyhedron
In elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...
in three dimensions, polyhedra such as the regular dodecahedron with the property that three faces meet at every vertex.
An arbitrary graph embedding
Graph embedding
In topological graph theory, an embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:...
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 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. TaitPeter Guthrie Tait
Peter Guthrie Tait FRSE was a Scottish mathematical physicist, best known for the seminal energy physics textbook Treatise on Natural Philosophy, which he co-wrote with Kelvin, and his early investigations into knot theory, which contributed to the eventual formation of topology as a mathematical...
conjectured that every cubic polyhedral graph
Polyhedral graph
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs...
has a Hamiltonian circuit. William Thomas Tutte provided a counter-example to Tait's conjecture
Tait's conjecture
In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle through all its vertices". It was proposed by and disproved by , who constructed a counterexample with 25 faces, 69 edges and 46 vertices...
, the 46-vertex Tutte graph
Tutte graph
In the mathematical field of graph theory, the Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte. It has chromatic number 3, chromatic index 3, girth 4 and diameter 8....
, in 1946. In 1971, Tutte conjectured that all bicubic graphs are Hamiltonian. However, Joseph Horton provided a counterexample on 96 vertices, the Horton graph
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...
. Later, Mark Ellingham constructed two more counterexamples : the Ellingham-Horton graph
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. Ellingham, their discoverers. These two graphs provide...
s. Barnette's conjecture
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...
, 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
LCF notation
In combinatorial mathematics, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by Coxeter and Frucht, for the representation of cubic graphs that are Hamiltonian. Since the graphs are Hamiltonian, the vertices can be arranged in a cycle, which accounts for two edges...
allows it to be represented concisely.
If a cubic graph is chosen uniformly at random
Random graph
In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
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
David Eppstein
David Arthur Eppstein is an American computer scientist and mathematician. He is professor of computer science at University of California, Irvine. He is known for his work in computational geometry, graph algorithms, and recreational mathematics.-Biography:Born in England of New Zealander...
conjectured that every n-vertex cubic graph has at most 2n/3 (approximately 1.260n) distinct Hamiltonian cycles, and provided examples of cubic graphs with that many cycles. The best upper bound that has been proven on the number of distinct Hamiltonian cycles is 1.276n.
Other properties
The pathwidth of any n-vertex cubic graph is at most n/6. However, the best known lower bound on the pathwidth of cubic graphs is smaller, 0.082n.It follows from the handshaking lemma
Handshaking lemma
In graph theory, a branch of mathematics, the handshaking lemma is the statement that every finite undirected graph has an even number of vertices with odd degree...
, proven by Leonhard Euler
Leonhard Euler
Leonhard Euler was a pioneering Swiss mathematician and physicist. He made important discoveries in fields as diverse as infinitesimal calculus and graph theory. He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion...
in 1736 as part of the first paper on graph theory, that every cubic graph has an even number of vertices.
Petersen
Julius Petersen
Julius 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...
's theorem states that every cubic bridgeless
Bridge (graph theory)
In 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....
graph has a perfect matching.
Lovász
László Lovász
László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
and Plummer 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 2n/3656 perfect matchings.
Algorithms and complexity
Several researchers have studied the complexity of exponential time algorithms restricted to cubic graphs. For instance, by applying dynamic programmingDynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
to a path decomposition
Path decomposition
In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G...
of the graph, Fomin and Høie showed how to find their maximum independent sets in time O(2n/6 + o(n)). The travelling salesman problem
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
can be solved in cubic graphs in time O(1.251n).
Several important graph optimization problems are APX hard
APX
In complexity theory the class APX is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant...
, meaning that, although they have approximation algorithm
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
s whose approximation ratio 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
Vertex cover
In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set....
, maximum independent set, minimum dominating set
Dominating set
In graph theory, a dominating set for a graph G = is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge...
, and maximum cut
Maximum cut
For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the max-cut problem.The problem can be stated simply as follows...
.
The crossing number
Crossing number (graph theory)
In graph theory, the crossing number cr of a graph G is the lowest number of edge crossings of a planar drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero.The concept originated in...
(the minimum number of edges which cross in any graph drawing
Graph drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
) of a cubic graph is also NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
for cubic graphs but may be approximated.