The number of perfect matchings of a k-pfaffian graph can be counted by computing a linear combination of the pfaffians of k matrices. The pfaffian number of a graph G is the smallest integer k such that G is k-pfaffian. We present the first known lower bounds for the pfaffian number of graphs. As an intermediate step, we prove an upper bound for the rank of two matrices related to their Khatri-Rao product. One of the consequences of the found lower bounds is the existence of graphs whose pfaffian numbers are arbitrarily large.

Given a graph G, an orientation D of G and a perfect matching M of G, it is possible to define the sign (-1 or +1) of M in D. Given k orientations of a graph G, a signature matrix A has rows corresponding to perfect matchings of G and columns corresponding to each of these k orientations such that each entry aij is the sign of the i-th perfect matching on the j-th orientation. A graph is k-Pfaffian if there is a set of k orientations whose signature matrix A is such that the linear system Ax = 1 has a solution. The Pfaffian number of a graph G is the smallest k such that G is k-Pfaffian. We present in this paper a characterization of the signature matrices of graphs with Pfaffian number 6.