# All Perfect Matchings on a Square Lattice

Is there a way to quickly display all the perfect matchings of the vertices of a square lattice?

The following code only finds one:

HighlightGraph[
GridGraph[{4, 4}, VertexStyle -> White,
EdgeStyle -> Gray], {Style[
FindIndependentEdgeSet[GridGraph[{4, 4}]], Blue,Thick]}] • I will recommend IGLargestIndependentVertexSets in my this answer – yode May 23 '17 at 8:24
• Yes it will run faster I think. – Alexander Kartun-Giles May 23 '17 at 8:30

Ok, so the trick I have used is to construct the LineGraph of the lattice, and then find all its largest independent vertex sets.

On e.g. the 4 x 4 square lattice, the following code outputs all 36 perfect matchings of the vertices:

    perfectsets[g_] := Module[{},
allsets = FindIndependentVertexSet[LineGraph[g], Infinity, All];
maximalsets = {};
For[i = 1, i <= Length[allsets], i++,
If[Length[allsets[[i]]] == 2 n,
maximalsets = Append[maximalsets, allsets[[i]]];
];]; maximalsets];

n = 4;
g = GridGraph[{n, n}, VertexStyle -> White,
EdgeStyle -> {Gray, Thick}];

matchings = EdgeList[g][[#]] & /@ perfectsets[g];
ListofPerfectMatchings =
Table[HighlightGraph[
GridGraph[{n, n}, VertexStyle -> White,
EdgeStyle -> Gray], {Style[matchings[[i]], Blue, Thick]}], {i, 1,
Length[matchings]}]


i.e. • Also note $n$ must be even for a perfect matching to exist. – Alexander Kartun-Giles May 23 '17 at 8:35