Number of perfect matchings of the Dodecahedron

Question

This question seems just to be an elementary enumeration problem, but I believe something deeper might be involved:

How many perfect matchings does a dodecahedron graph have?

Here the dodecahedron graph has 20 vertexes, 12 faces and 30 edges.

I know this graph is really a planar graph so one can draw its Kasteleyn orientation and then do the pfaffian calculation, but obviously this is not a clever way(one get a 20 x 20 matrix). This does not utilize the plenty symmetry of the graph.

I wonder whether there is some other way that does not use the pfaffian aproach. For example a trick like graph transformation or of a divide-and-conquer style. I am interested in all kinds of solutions to this problem, thanks in advance.

further explanations: here by "something deep" I mean: (but not limited to) 1. use the symmetry ($A_5$) to simplify the calculation of the pfaffian, or deduce some other way to enumerate the matching. 2. Tricks like the $Y-\Delta$ transformations that can be generalized to general cellular graphs; 3. By a dived-and -conquer way, I mean divide the matchings into subcases and then derive a recurrence relations.

Answer 1

A related question arose in the work of Aitchison-Rubinstein on the "dodecahedral knots". They associated knots to "2-colorings" of cubic planar graphs. This is a coloring of the faces by black and white colors, so that at each vertex 2 colors appear. Up to exchanging the colors and symmetry, there are two such colorings of the dodecahedron (although they don't explain in the paper how they enumerated them, I once carried through the computation by hand, which is not too hard).

These are equivalent to perfect matchings, since removing a perfect matching from a cubic graph gives a 1-manifold going through every vertex, and dividing the faces into black and white regions giving a 2-coloring, and vice-versa.

One easily sees that there are 6 matchings associated to the first coloring (one has 12 choices for the isolated black face, quotient exchanging the colors) and 30 for the second coloring (there are 12 choices for the central black face, and 5 for the adjacent face, modulo exchanging colors; note the other black face at the end of the snake of black faces gives the reflected coloring).

Answer 2

Here's a proof I concocted, utilising our favourite graph:

Consider the Petersen graph $P$, obtained from the dodecahedral graph $D$ by quotienting out by the antipodal map $\theta : D \rightarrow P$. Now suppose we have a matching $M \subset E(D)$, and label each edge $e \in P$ by the size of the preimage $M \cap \theta^{-1}(e)$.

We have assigned each edge of $P$ a label $0$, $1$ or $2$, such that the sum of the labels around each vertex is $2$. Consequently, one can deduce that the $2$-edges are isolated and the $1$-edges form cycles. Since $P$ is non-Hamiltonian and girth-$5$, the only possibilities are:

• Two 5-cycles of 1-edges;
• One 8-cycle of 1-edges and one 2-edge;
• One 6-cycle of 1-edges and two 2-edges;
• Five 2-edges.

In the first case, the preimages (under $\theta$) of the two 5-cycles must be centrally symmetric 10-cycles, which therefore intersect (contradiction).

In the second case, removing an edge of $P$ gives a graph with a unique Hamiltonian 8-cycle $C$, which leads to two possible matchings in the preimage. Since $P$ has $15$ edges, this gives $30$ matchings overall.

The third case is impossible, since after removing an edge of $P$, we cannot find a $6$-cycle.

The fourth case reduces exactly to counting matchings of the Petersen graph. By complementation, this is equivalent to counting partitions of the edges of the Petersen graph into disjoint cycles (the only possibilities being pairs of disjoint $5$-cycles), which is just half of the number of $5$-cycles in the Petersen graph (namely $12$). Hence, we obtain another $6$ matchings in this manner.

Consequently, there are $36$ matchings of the dodecahedron.

Answer 3

A number of clever techniques are recalled (with references) and a new one introduced in the paper by Shinsaku Fujita (2013) (MATCH communications in math. and computer chemistry).