On the Pfaffian Number of Graphs

In 2006, Norine conjectured that a graph is k-Pfaffian but not (k−1)-Pfaffian if and only if k is a power of four [Norine, S., Drawing 4-Pfaffian graphs on the torus, Combinatorica (accepted for publication), http://www.math.princeton.edu/~snorin/papers.html.]. Recently, we presented a graph that is a counter-example to that conjecture [Miranda, A. A. A. and C. L. Lucchesi, Matching signatures and Pfaffian graphs, Technical report, Institute of Computing – University of Campinas – UNICAMP (2009). URL http://www.ic.unicamp.br/~reltech/2009/09-06.pdf]. In this article, we present an alternative proof that this graph is a counter-example to the conjecture. In fact, we present a graph that is not 4-Pfaffian and give a simple proof that it is 10-Pfaffian, using new methods.