View source for Cubic graph

{{Short description|Graph with all vertices of degree 3}}
{{distinguish|text=[[Graph of a function|graphs]] of [[cubic function]]s, [[hypercube graph]], [[cube graph]], [[cubical graph]]}}

[[File:Petersen1 tiny.svg|thumb|right|The [[Petersen graph]] is a cubic graph.]]

[[File:Biclique K 3 3.svg|thumb|180px|right|The [[complete bipartite graph]] <math>K_{3,3}</math> is an example of a bicubic graph]]

In the [[mathematics|mathematical]] field of [[graph theory]], a  '''cubic graph''' is a [[Graph (discrete mathematics)|graph]] in which all [[vertex (graph theory)|vertices]] have [[degree (graph theory)|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]].

==Symmetry==
In 1932, [[R. M. Foster|Ronald M. Foster]] began collecting examples of cubic [[symmetric graph]]s, forming the start of the [[Foster census]].<ref name="Ref_Foster">{{Citation|first1=R. M.|last1=Foster|title=Geometrical Circuits of Electrical Networks|journal=[[Transactions of the American Institute of Electrical Engineers]]|volume=51|pages=309–317|year=1932|doi=10.1109/T-AIEE.1932.5056068|issue=2|s2cid=51638449}}.</ref> Many well-known individual graphs are cubic and symmetric, including the [[Water, gas, and electricity|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 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.<ref>{{Citation
 | doi = 10.4153/CJM-1959-057-2
 | last = Tutte
 | first = W. T.
 | journal = Can. J. Math.
 | pages = 621–624
 | title = On the symmetry of cubic graphs
 | url = http://cms.math.ca/cjm/v11/p621
 | volume = 11
 | year = 1959
 | s2cid = 124273238
 | doi-access = free
 | access-date = 2010-07-21
 | archive-date = 2011-07-16
 | archive-url = https://web.archive.org/web/20110716145555/http://cms.math.ca/cjm/v11/p621
 | url-status = dead
 }}.</ref>

[[Semi-symmetric graph|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 five smallest cubic graphs without any symmetries:<ref>{{citation|last1=Bussemaker|first1=F. C.|last2=Cobeljic|first2=S.|last3=Cvetkovic|first3=D. M.|last4=Seidel|first4=J. J.|publisher=Dept. of Mathematics and Computing Science, Eindhoven University of Technology|series=EUT report|title=Computer investigation of cubic graphs|url=https://research.tue.nl/en/publications/computer-investigation-of-cubic-graphs|volume=76-WSK-01|year=1976}}</ref> it possesses only a single [[graph automorphism]], the identity automorphism.<ref>{{Citation | last1=Frucht | first1=R. | title=Graphs of degree three with a given abstract group | doi = 10.4153/CJM-1949-033-6 | mr=0032987 | year=1949 | journal=[[Canadian Journal of Mathematics]] | issn=0008-414X | volume=1 | issue=4 | pages=365–378| s2cid=124723321 | doi-access=free }}.</ref>

==Coloring and independent sets==
According to [[Brooks' theorem]] every connected cubic graph other than the [[complete graph]] ''K''<sub>4</sub> has a [[vertex coloring]] with at most three colors. Therefore, every connected cubic graph other than ''K''<sub>4</sub> has an [[independent set (graph theory)|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 matching]]s. By [[Kőnig's theorem (graph theory)|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 [[Snark (graph theory)|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.<ref>{{citation
 | doi = 10.2307/2319844
 | last = Isaacs | first = R.
 | author-link=Rufus Isaacs (game theorist)
 | issue = 3
 | journal = [[American Mathematical Monthly]]
 | pages = 221–239
 | title = Infinite families of nontrivial trivalent graphs which are not Tait colorable
 | jstor = 2319844
 | volume = 82
 | year = 1975}}.</ref>

==Topology and geometry==
Cubic graphs arise naturally in [[topology]] in several ways.  For example, the cubic graphs with ''2g-2'' vertices describe the different ways of cutting a [[surface]] of genus ''g ≥ 2'' into [[Pair of pants (mathematics) | pairs of pants]]. If one considers a [[Graph (discrete mathematics)|graph]] to be a 1-dimensional [[CW complex]], cubic graphs are ''[[Generic property|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 [[polyhedron|simple polyhedra]] in three dimensions, polyhedra such as the [[regular dodecahedron]] with the property that three faces meet at every vertex.

[[File:Graph-encoded map.svg|thumb|upright=1.8|Representation of a planar embedding as a graph-encoded map]]
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 (geometry)|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.<ref>{{citation
 | last1 = Bonnington | first1 = C. Paul
 | last2 = Little | first2 = Charles H. C.
 | publisher = Springer-Verlag
 | title = The Foundations of Topological Graph Theory
 | year = 1995}}.</ref>

==Hamiltonicity==
There has been much research on [[Hamiltonian cycle|Hamiltonicity]] of cubic graphs. In 1880, [[Peter Guthrie Tait|P.G. Tait]] 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]].<ref name="Ref_a">Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.</ref> Later, [[Mark Ellingham]] constructed two more counterexamples: the [[Ellingham–Horton graph]]s.<ref name="Ref_b">Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.</ref><ref name="Ref_c">{{Citation|last1=Ellingham|first1=M. N.|last2=Horton|first2=J. D.|title= Non-Hamiltonian 3-connected cubic bipartite graphs|journal=[[Journal of Combinatorial Theory]]|series=Series B| volume=34| pages=350–353| year=1983| doi=10.1016/0095-8956(83)90046-1|issue=3|doi-access=free}}.</ref> [[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 [[random graph|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.<ref>{{citation
 | last1 = Robinson | first1 = R.W.
 | last2 = Wormald | first2 = N.C.
 | doi = 10.1002/rsa.3240050209
 | issue = 2
 | journal = Random Structures and Algorithms
 | pages = 363–374
 | title = Almost all regular graphs are Hamiltonian
 | volume = 5
 | year = 1994}}.</ref>

[[David Eppstein]] conjectured that every ''n''-vertex cubic graph has at most 2<sup>''n''/3</sup> (approximately 1.260<sup>''n''</sup>) distinct Hamiltonian cycles, and provided examples of cubic graphs with that many cycles.<ref>{{citation
 | last = Eppstein | first = David | author-link = David Eppstein
 | arxiv = cs.DS/0302030 | issue = 1
 | journal = [[Journal of Graph Algorithms and Applications]]
 | pages = 61–81
 | title = The traveling salesman problem for cubic graphs
 | url = http://jgaa.info/accepted/2007/Eppstein2007.11.1.pdf
 | volume = 11
 | year = 2007 | doi=10.7155/jgaa.00137}}.</ref> The best proven estimate for the number of distinct Hamiltonian cycles is <math> O({1.276}^n)</math>.<ref>{{citation
 | last = Gebauer
 | first = H.
 | contribution = On the number of Hamilton cycles in bounded degree graphs
 | title = Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08)
 | url = https://epubs.siam.org/doi/pdf/10.1137/1.9781611972986.8
 | year = 2008
 | pages = 241–248
 | doi = 10.1137/1.9781611972986.8
 | isbn = 9781611972986
 }}.</ref>

==Other properties==
{{unsolved|mathematics|What is the largest possible [[pathwidth]] of an <math>n</math>-vertex cubic graph?}}
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.<ref name="fh06">{{citation
 | last1 = Fomin | first1 = Fedor V.
 | last2 = Høie | first2 = Kjartan
 | doi = 10.1016/j.ipl.2005.10.012
 | issue = 5
 | journal = [[Information Processing Letters]]
 | pages = 191–196
 | title = Pathwidth of cubic graphs and exact algorithms
 | volume = 97
 | year = 2006}}.</ref>

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 [[bridge (graph theory)|bridgeless]] graph has a [[perfect matching]].<ref name="Pet1891">{{Citation
 | last1 = Petersen | first1 = Julius Peter Christian
 | issue = 15
 | journal = [[Acta Mathematica]]
 | pages = 193–220
 | title = Die Theorie der regulären Graphs (The theory of regular graphs)
 | doi=10.1007/BF02392606
 | year = 1891
 | volume = 15| s2cid = 123779343
 | url = https://zenodo.org/record/2304433
 | doi-access = free
 }}.</ref>
[[László Lovász|Lovász]] and [[Michael D. Plummer|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 2<sup>n/3656</sup> perfect matchings.<ref name="EKKKN11">{{citation
 | last1 = Esperet | first1 = Louis
 | last2 = Kardoš | first2 = František
 | last3 = King | first3 = Andrew D.
 | last4 = Kráľ | first4 = Daniel | author4-link = Daniel Kráľ
 | last5 = Norine | first5 = Serguei
 | doi = 10.1016/j.aim.2011.03.015
 | issue = 4
 | journal = [[Advances in Mathematics]]
 | pages = 1646–1664
 | title = Exponentially many perfect matchings in cubic graphs
 | year = 2011
 | volume = 227| arxiv = 1012.2878
 | s2cid = 4401537
 }}.</ref>

==Algorithms and complexity==
Several researchers have studied the complexity of [[exponential time]] algorithms restricted to cubic graphs. For instance, by applying [[dynamic programming]] to a [[path decomposition]] of the graph, Fomin and Høie showed how to find their [[maximum independent set]]s in time 2<sup>''n''/6&nbsp;+&nbsp;o(''n'')</sup>.<ref name="fh06"/> The [[travelling salesman problem]] in cubic graphs can be solved in time O(1.2312<sup>''n''</sup>) and polynomial space.<ref name="XiaoNag13">{{citation
 |first1=Mingyu
 |last1=Xiao
 |first2=Hiroshi
 |last2=Nagamochi
 |series=Lecture Notes in Computer Science
 |publisher=Springer-Verlag
 |title=Theory and Applications of Models of Computation
 |contribution=An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure
 |year=2013
 |doi=10.1007/978-3-642-38236-9_10
 |volume=7876
 |pages=96–107
 |isbn=978-3-642-38236-9|arxiv=1212.6831
 }}.</ref><ref>{{citation
 |  first1 = Mingyu | last1 = Xiao
 |  first2 = Hiroshi | last2 = Nagamochi
 | arxiv = 1212.6831 
 | title = An Exact Algorithm for TSP in Degree-3 Graphs Via Circuit Procedure and Amortization on Connectivity Structure
 | journal = Algorithmica
 | year = 2012| volume = 74
 | issue = 2
 | pages = 713–741
 | doi = 10.1007/s00453-015-9970-4
 |bibcode = 2012arXiv1212.6831X| s2cid = 7654681
 }}.</ref>

Several important graph optimization problems are [[APX|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 scheme]]s whose approximation ratio tends to 1 unless [[P vs NP problem|P=NP]]. These include the problems of finding a minimum [[vertex cover]], [[maximum independent set]], minimum [[dominating set]], and [[maximum cut]].<ref>{{citation
 | last1 = Alimonti | first1 = Paola
 | last2 = Kann | first2 = Viggo
 | doi = 10.1016/S0304-3975(98)00158-3
 | issue = 1–2
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | pages = 123–134
 | title = Some APX-completeness results for cubic graphs
 | volume = 237
 | year = 2000| doi-access = free
 }}.</ref>
The [[Crossing number (graph theory)|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.<ref name="Hlinny2006">{{citation|first=Petr|last=Hliněný|title=Crossing number is hard for cubic graphs|journal=[[Journal of Combinatorial Theory]]|series=Series B|volume=96|issue=4|pages=455–471|year=2006|doi=10.1016/j.jctb.2005.09.009|doi-access=free}}.</ref>
The [[Travelling Salesman Problem]] on cubic graphs has been proven to be [[NP-hard]] to approximate to within any factor less than 1153/1152.<ref>{{citation
 |  first1 = Marek | last1 = Karpinski
 |  first2 = Richard | last2 = Schmied
 | arxiv = 1304.6800 
 | title = Approximation Hardness of Graphic TSP on Cubic Graphs
 | year = 2013|bibcode = 2013arXiv1304.6800K}}.</ref>

==See also==
{{commons category|3-regular graphs}}
* [[Table of simple cubic graphs]]

== References ==
{{reflist|30em}}

==External links==
*{{cite web|url=http://mapleta.maths.uwa.edu.au/~gordon/remote/foster/|first1=Gordon|last1=Royle|title=Cubic symmetric graphs (The Foster Census)|url-status=dead|archive-url=https://web.archive.org/web/20111023234733/http://mapleta.maths.uwa.edu.au/~gordon/remote/foster/|archive-date=2011-10-23}}
*{{mathworld|urlname=BicubicGraph|title=Bicubic Graph}}
*{{mathworld|urlname=CubicGraph|title=Cubic Graph}}
* {{cite journal|first1=Gunnar|last1=Brinkmann | first2=Jan | last2=Goedgebeur | first3=Nico|last3=Van Cleemput |title=The history of the generation of cubic graphs| year=2013|journal=Int. J. Chem. Modeling| volume=5|number=2-3|pages=67-89| url=https://people.cs.kuleuven.be/~jan.goedgebeur/papers/paper-cubic_graphs_survey.pdf|issn=1941-3955|publisher=Nova Science}}

[[Category:Graph families]]
[[Category:Regular graphs]]