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. 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 sets in time 2n/6 + o(n). The travelling salesman problem in cubic graphs can be solved in time O(1.2312n) and polynomial space. Several important graph optimization problems are APX hard, meaning that, although they have approximation algorithms 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. The Travelling Salesman Problem on cubic graphs has been proven to be NP-hard to approximate to within any factor less than 1153/1152. See also Table of simple cubic graphs References External links Graph families Regular graphs