Editing Cubic graph (section)

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