quality:correction
Explanation

The main insight is that every non-zero term in the Pfaffian of the adjacency matrix of a graph G corresponds to a perfect matching. Thus, if one can find an orientation of G to align all signs of the terms in Pfaffian (no matter + or -), then the absolute value of the Pfaffian is just the number of perfect matchings in G. The FKT algorithm does such a task for a planar graph G. The orientation it finds is called a Pfaffian orientation.

Let G = (V, E) be an undirected graph with adjacency matrix A. Define PM (n) to be the set of partitions of n elements into pairs, then the number of perfect matchings in G is

Closely related to this is the Pfaffian for an n by n matrix A

where sgn(M) is the sign of the permutation M. A Pfaffian orientation of G is a directed graph H with adjacency matrix B such that pf(B) = PerfMatch(G). In 1967, Kasteleyn proved that planar graphs have an efficiently computable Pfaffian orientation. Specifically, for a planar graph G, let H be a directed version of G where an odd number of edges are oriented clockwise for every face in a planar embedding of G. Then H is a Pfaffian orientation of G.

Finally, for any skew-symmetric matrix A,

where det(A) is the determinant of A. This result is due to Arthur Cayley. Since determinants are efficiently computable, so is PerfMatch(G).