Editing Cubic graph (section)

==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>