Find all perfect matchings of a Graph

A quick way to program this is through finding all maximum independent vertex sets of the line graph:

lg = LineGraph[g];
EdgeList[g][[#]] & /@ 
 FindIndependentVertexSet[lg, Length /@ FindIndependentVertexSet[lg], All]

HighlightGraph[g, #] & /@ %

I've implemented the algorithm given in the paper

Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs.

This algorithm takes as input a directed bipartite graph and should give a list of all perfect matchings as output.

EnumPerfectMatchings[G_] := 
 EnumPerfectMatchingsIter[G, FindIndependentEdgeSet[G]]

EnumPerfectMatchingsIter[G_, M_] := If[
  Length[EdgeList[G]] == 0,
  {M},
  Module[{DGM, DM, DG, NewM, c, e, Gp, Gm, p},
   DM = M;
   DG = DirectedEdge @@@ 
     Reverse /@ List @@@ Complement[EdgeList[G], M];
   DGM = Graph[VertexList[G], Join[DM, DG]];
   c = FindCycle[DGM];
   If[Length[c] != 0, c = Flatten[c], Return[{M}]];
   c = Transpose@Partition[c, 2];
   If[MemberQ[DG, c[[1, 1]]], c = Reverse[c]];
   c = {c[[1]], DirectedEdge @@@ Reverse /@ List @@@ c[[2]]};
   NewM = Join[Complement[M, c[[1]]], c[[2]]];
   e = c[[1, 1]];
   p = List @@ e;
   Gp = Graph[Complement[VertexList[G], p], 
     Select[EdgeList[G], Intersection[List @@ #, p] == {} &]];
   Gm = Graph[VertexList[G], Complement[EdgeList[G], {e}]];
   Join[EnumPerfectMatchingsIter[Gm, NewM], 
    Map[Append[#, e] &, 
     EnumPerfectMatchingsIter[Gp, Complement[M, {e}]]]]
   ]
  ]

For the graph given in the question it returns the correct result 0.007 sec on my machine.

You can do this with the following code:

points = {1, 2, 4, 6, 3, 8, 5, 7};
edges = {1 <-> 2, 1 <-> 4, 1 <-> 6, 3 <-> 4, 3 <-> 6, 3 <-> 8, 
          5 <-> 6, 5 <-> 8, 5 <-> 2, 7 <-> 8, 7 <-> 2, 7 <-> 4};

tmp=Table[FindIndependentEdgeSet[Graph[i, edges]], {i,Permutations[points]}]// DeleteDuplicates;
tmp=tmp/.UndirectedEdge[x_, y_] /; x > y :> UndirectedEdge[y, x];
Table[Sort[i, #1[[1]] < #2[[1]] &], {i, tmp}] // DeleteDuplicates

which will try all vertex permutations, whose order in turn is used by FindIndependentEdgeSet to produce its result.

{{1 <-> 2, 3 <-> 6, 4 <-> 7, 5 <-> 8}, {1 <-> 2, 3 <-> 4, 5 <-> 6, 
  7 <-> 8}, {1 <-> 2, 3 <-> 8, 4 <-> 7, 5 <-> 6}, {1 <-> 4, 2 <-> 5, 
  3 <-> 6, 7 <-> 8}, {1 <-> 4, 2 <-> 7, 3 <-> 6, 5 <-> 8}, {1 <-> 4, 
  2 <-> 7, 3 <-> 8, 5 <-> 6}, {1 <-> 6, 2 <-> 5, 3 <-> 4, 
  7 <-> 8}, {1 <-> 6, 2 <-> 7, 3 <-> 4, 5 <-> 8}, {1 <-> 6, 2 <-> 5, 
  3 <-> 8, 4 <-> 7}}