Counting the number of perfect matchings in arbitrary graphs is a # P-complete problem. However, for some restricted classes of graphs the problem can be solved efficiently. In the case of planar graphs, and even for K 3 3 -free graphs, Vazirani showed that it is in NC 2 . The technique there is to compute a Pfaffian orientation of a graph.

In the case of K 5 -free graphs, this technique will not work because some K 5 -free graphs do not have a Pfaffian orientation. We circumvent this problem and show that the number of perfect matchings in K 5 -free graphs can be computed in polynomial time. We also parallelize the sequential algorithm and show that the problem is in TC 2 .