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 and for the planar graphs by Chudnovsky and Seymour . Both of these results are difficult. In general, the conjecture is widely open; see for a linear lower bound obtained so far...