This is a very easy problem for the sizes you are proposing... a 20-vertex quartic graph seems to only have a few hundred perfect matchings (random sample), and it takes my computer approximately 2/100ths of a second to count them.

This is actually an ideal application for my favourite constraint satisfaction programming solver, namely Minion. It took me 15 minutes to write and test a program that converts a graph into a suitable Minion program, and then the Minion program takes the above-mentioned 2/100ths of a second.

I used to write lots of back-tracking programs, but Minion is so good that for almost all applications, it beats a bespoke program by a wide margin, and so nowadays I almost never write my own back-track, but just convert to a Minion program!

Here's an example of the Minion program for a 20-vertex graph - there are 40 boolean variables, one for each edge, stored in an array called "ed". The line "sumgeq(ed,10)" says that we need the sum of the 40 variables in the array to be at least 10 (in fact we want exactly 10, but in a strange decision, Minion only allows you to specify equality as a combination of two inequalities). Then for each VERTEX, we need exactly one edge to be chosen, and so we have 40 constraints in 20 pairs, with each pair saying that "at least one", and "at most one", of the edges incident with a particular vertex is chosen.

Running this code then takes a few hundredths of a second and produces the answer that there are exactly 364 perfect matchings.

```
MINION 3
**VARIABLES**
BOOL ed[40]
**CONSTRAINTS**
sumgeq(ed,10)
sumleq([ed[0],ed[1],ed[2],ed[3]],1)
sumleq([ed[4],ed[5],ed[6],ed[7]],1)
sumleq([ed[8],ed[9],ed[10],ed[11]],1)
sumleq([ed[8],ed[12],ed[13],ed[14]],1)
sumleq([ed[0],ed[9],ed[15],ed[16]],1)
sumleq([ed[15],ed[17],ed[18],ed[19]],1)
sumleq([ed[16],ed[20],ed[21],ed[22]],1)
sumleq([ed[4],ed[23],ed[24],ed[25]],1)
sumleq([ed[1],ed[12],ed[17],ed[23]],1)
sumleq([ed[2],ed[20],ed[26],ed[27]],1)
sumleq([ed[13],ed[26],ed[28],ed[29]],1)
sumleq([ed[24],ed[30],ed[31],ed[32]],1)
sumleq([ed[10],ed[30],ed[33],ed[34]],1)
sumleq([ed[5],ed[33],ed[35],ed[36]],1)
sumleq([ed[18],ed[28],ed[31],ed[37]],1)
sumleq([ed[14],ed[25],ed[37],ed[38]],1)
sumleq([ed[6],ed[19],ed[21],ed[39]],1)
sumleq([ed[11],ed[27],ed[29],ed[35]],1)
sumleq([ed[3],ed[7],ed[22],ed[39]],1)
sumleq([ed[32],ed[34],ed[36],ed[38]],1)
sumgeq([ed[0],ed[1],ed[2],ed[3]],1)
sumgeq([ed[4],ed[5],ed[6],ed[7]],1)
sumgeq([ed[8],ed[9],ed[10],ed[11]],1)
sumgeq([ed[8],ed[12],ed[13],ed[14]],1)
sumgeq([ed[0],ed[9],ed[15],ed[16]],1)
sumgeq([ed[15],ed[17],ed[18],ed[19]],1)
sumgeq([ed[16],ed[20],ed[21],ed[22]],1)
sumgeq([ed[4],ed[23],ed[24],ed[25]],1)
sumgeq([ed[1],ed[12],ed[17],ed[23]],1)
sumgeq([ed[2],ed[20],ed[26],ed[27]],1)
sumgeq([ed[13],ed[26],ed[28],ed[29]],1)
sumgeq([ed[24],ed[30],ed[31],ed[32]],1)
sumgeq([ed[10],ed[30],ed[33],ed[34]],1)
sumgeq([ed[5],ed[33],ed[35],ed[36]],1)
sumgeq([ed[18],ed[28],ed[31],ed[37]],1)
sumgeq([ed[14],ed[25],ed[37],ed[38]],1)
sumgeq([ed[6],ed[19],ed[21],ed[39]],1)
sumgeq([ed[11],ed[27],ed[29],ed[35]],1)
sumgeq([ed[3],ed[7],ed[22],ed[39]],1)
sumgeq([ed[32],ed[34],ed[36],ed[38]],1)
**EOF**
```

countingperfect matchings in a planar graph. Is this enough? – John Wiltshire-Gordon Feb 28 '12 at 18:24