A classic theorem of Petersen claims that every cubic (each degree 3) graph with no cutedge has a perfect matching. A well-known conjecture of Lovasz and Plummer from the mid-1970’s, still open, asserts that for every cubic graph G with no cutedge, the number of perfect matchings of G is exponential in |V(G)|. The assertion of the conjecture was proved for the kưregular bipartite graphs by Schrijver [Sch98] and for the planar graphs by Chudnovsky and Seymour [CS08]. Both of these results are difficult. In general, the conjecture is widely open; see [KSS08] for a linear lower bound obtained so far.