A 3-edge-coloring is known as a Tait coloring, and forms a partition of the edges of the graph into three perfect matchings.
For example, the cubic graphs with 2g-2 vertices describe the different ways of cutting a surface of genus g ≥ 2 into pairs of pants.
Tait conjectured that every cubic polyhedral graph has a Hamiltonian circuit.
When a cubic graph is Hamiltonian, LCF notation allows it to be represented concisely.
Petersen's theorem states that every cubic bridgeless graph has a perfect matching.
[14] 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.
[15] 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 sets in time 2n/6 + o(n).
[13] The travelling salesman problem in cubic graphs can be solved in time O(1.2312n) and polynomial space.
[19] The Travelling Salesman Problem on cubic graphs has been proven to be NP-hard to approximate to within any factor less than 1153/1152.