ABSTRACT
If A is a skew symmetric matrix then det A is the square of a polynomial in the entries of A. This polynomial is known as the Pfaffian of A, and we denote it by Sym(pf A). It is identically zero when n is odd. Tutte derived his famous characterisation of the graphs with no perfect matchings by using the Pfaffian. This chapter provides a combinatorial approach to its properties. Everything rests on the fact that if A is n × n then pf A can be expressed as a weighted sum over the perfect matchings of Kn , in close analogy to the way det A can be expressed as a weighted sum over the permutations of {1,…, n}. This raises a question: Given a graph G on n vertices, can we construct an n × n skew symmetric matrix whose Pfaffian is equal to the number of perfect matchings of G? We present Kasteleyn’s proof that this is always possible if G is planar.
