Matching signatures and Pfaffian graphs

Perfect matchings of k -Pfaffian graphs may be enumerated in polynomial time on the number of vertices, for fixed k . In general, this enumeration problem is # P -complete. We give a Composition Theorem of 2 r -Pfaffian graphs from r Pfaffian spanning subgraphs. Constructions of k -Pfaffian graphs known prior to this seem to be of a very different and essentially topological nature. We apply our Composition Theorem to produce a bipartite graph on 10 vertices that is 6-Pfaffian but not 4-Pfaffian. This is a counter-example to a conjecture of Norine (2009) [8], which states that the Pfaffian number of a graph is a power of four.