Which integers occur as Pfaffian numbers of graphs? The Miranda–Lucchesi parity and realizability conjecture

The Pfaffian number pf(G) of a graph G is the least number k of orientations of G whose induced signs on perfect matchings combine, with real coefficients, to the constant 1 — equivalently, the least number of Pfaffian evaluations needed to count the perfect matchings of G exactly. Kasteleyn's theory and the Galluccio–Loebl/Tesler genus bound show pf(G) is finite, Norine proved that 3 and 5 are not Pfaffian numbers, and Miranda and Lucchesi constructed a graph G_19 with pf(G_19)=6, refuting Norine's conjecture that every Pfaffian number is a power of four. Miranda and Lucchesi then conjectured (Conjecture 20 of their 2011 paper) that pf(G) is even and at least 4 whenever it exceeds 1, and that every even integer k≥4 is the Pfaffian number of some graph. As of 2026 this conjecture is no longer fully open: its parity half is false, since 13 is the Pfaffian number of $K_{3,3}\sqcup K_{3,3}$ (Pant and Singh, arXiv:2609.22928, 2026), while its realizability half and the full determination of which integers occur remain open. The exact Pfaffian numbers known are 1, 4, 6 and 13, and 2026 work proves the values are unbounded and can grow exponentially in the genus. The problem is to determine exactly which positive integers occur as Pfaffian numbers of graphs.

Background

A perfect matching of a graph is a set of pairwise disjoint edges covering every vertex. Counting perfect matchings is a fundamental problem of graph theory with applications in chemistry (enumeration of Kekulé structures, i.e. the perfect matchings of a molecular graph, which encode its possible chemical bonding patterns), statistical physics (dimer models, i.e. lattice models whose configurations are precisely the perfect matchings of a graph), and quantum mechanics; in general the problem is #P-complete — the counting analogue of NP-completeness (Valiant, 1979) — so no polynomial-time algorithm is expected. The classical polynomial-time escape for special graph classes is the Pfaffian method. Fix an orientation D of the graph G and a numbering of its vertices; each perfect matching M then determines a permutation, whose sign sgn(M,D) ∈ {+1,−1} is well defined independently of arbitrary choices. The orientation D is called a Pfaffian orientation if all perfect matchings of G have the same sign in D, and G is a Pfaffian graph if it admits one; in that case the number of perfect matchings equals, up to sign, the Pfaffian of the skew-symmetric adjacency matrix of D (a skew-symmetric matrix satisfies A^T = −A, and its Pfaffian is a polynomial in its entries whose square is the determinant, computable in polynomial time). Kasteleyn (1961, 1963) proved that every planar graph is Pfaffian.

For non-Pfaffian graphs, Norine (2009) introduced the following generalization: a graph G is k-Pfaffian if there exist orientations D_1,…,D_k of G and real coefficients α_1,…,α_k such that $\sum_{i=1}^{k}\alpha_i\,\operatorname{sgn}(M,D_i)=1$ for every perfect matching M of G — equivalently, the perfect-matching generating function of G is a linear combination of k Pfaffians. Miranda and Lucchesi reformulate this via the signature matrix: the matrix whose rows are the sign vectors $(\operatorname{sgn}(M,D_1),\dots,\operatorname{sgn}(M,D_k))$ over all perfect matchings M; G is k-Pfaffian exactly when the linear system given by this matrix with right-hand side the all-ones vector is solvable. The Pfaffian number pf(G) is the least such k; thus pf(G)=1 exactly for Pfaffian graphs, and pf(G) measures how many Pfaffian computations suffice for exact perfect-matching enumeration on G. A general account of the surrounding matching theory appears in the book of Lucchesi and Murty (2024).

Two results anchor the known landscape. First, Galluccio and Loebl (1999), and independently Tesler (2000), proved that every graph embeddable on an orientable surface of genus g (a surface with g handles; planar graphs are the case g=0) is $4^g$-Pfaffian, so every graph has a finite Pfaffian number. Second, Norine (2009) proved that every 3-Pfaffian graph is Pfaffian and every 5-Pfaffian graph is 4-Pfaffian, characterized the graphs of Pfaffian number four — for instance $\operatorname{pf}(K_{3,3})=4$, where $K_{3,3}$, the complete bipartite graph on 3+3 vertices, is the smallest non-Pfaffian graph — and conjectured that every Pfaffian number is a power of four. Miranda and Lucchesi (2011) refuted Norine's conjecture. Their composition theorem constructs 2r-Pfaffian graphs from r Pfaffian spanning subgraphs forming an r-decomposition (a partition of the perfect matchings with an odd-intersection parity condition), and their uniqueness theorem for signature matrices shows that the resulting bipartite graph $G_{19}$ — obtained from two disjoint copies of $K_{3,2}$ (the complete bipartite graph on 3+2 vertices) by joining their three-vertex parts with the nine edges of a $K_{3,3}$-tight cut (a cut that every perfect matching meets in exactly one edge), with two adjacent edges of that cut deleted — is a 10-vertex graph named for its 19 edges, and is 6-Pfaffian but not 4-Pfaffian, so $\operatorname{pf}(G_{19})=6$. In the literature to date, the only exact Pfaffian numbers of specific graphs that are known are 1, 4, 6 and 13, and in 2026 the Pfaffian number was shown to be unbounded and to grow at least exponentially in the genus; the fine structure of which integers occur at all remains unknown.

Problem Statement

Determine exactly which positive integers occur as Pfaffian numbers of graphs, where the Pfaffian number pf(G) of a graph G is the least positive integer k for which there exist orientations $D_1,\ldots,D_k$ of G and real coefficients $\alpha_1,\ldots,\alpha_k$ such that $\sum_{i=1}^{k}\alpha_i\,\operatorname{sgn}(M,D_i)=1$ for every perfect matching M of G. Miranda and Lucchesi (Conjecture 20 in Discrete Mathematics 311 (2011) 289–294; Conjecture 4.1 of their 2009 technical report) conjectured the following two claims, over all finite graphs with no restriction on the graph class:

(i) Parity: for every graph G with pf(G) > 1, pf(G) is even and pf(G) ≥ 4;

(ii) Realizability: for every even integer k ≥ 4 there exists a graph G with pf(G) = k.

Claim (i) is now known to be false — Pant and Singh exhibit a finite graph, $K_{3,3}\sqcup K_{3,3}$, with Pfaffian number 13 — so the conjecture as a whole fails and the set of Pfaffian numbers is not $\{1\}\cup\{4,6,8,\ldots\}$. It therefore remains to determine exactly which positive integers occur as Pfaffian numbers: equivalently, to settle claim (ii) and to determine which odd integers greater than 1 occur — for the odd values ≥ 7, which are Pfaffian numbers and whether infinitely many are. A refutation of (ii) must prove that some even integer ≥ 4 is not the Pfaffian number of any graph. Known partial results: pf = 1 characterizes Pfaffian graphs; 3 and 5 are not Pfaffian numbers (Norine); $\operatorname{pf}(K_{3,3})=4$ and $\operatorname{pf}(G_{19})=6$ (Miranda–Lucchesi); $\operatorname{pf}(K_{3,3}\sqcup K_{3,3})=13$, so 13 is a Pfaffian number and claim (i) is false (Pant–Singh 2026); Pfaffian numbers are unbounded (Junchaya–Miranda–Lucchesi 2026).

References

1. Alberto Alexandre Assis Miranda and Cláudio Leonardo Lucchesi, Matching signatures and Pfaffian graphs, Discrete Mathematics 311(4):289–294, 2011. DOI: 10.1016/j.disc.2010.10.014, https://doi.org/10.1016/j.disc.2010.10.014
2. Alberto Alexandre Assis Miranda and Cláudio Leonardo Lucchesi, Matching Signatures and Pfaffian Graphs, Technical Report IC-09-06, Instituto de Computação, Universidade Estadual de Campinas, 2009. https://ic.unicamp.br/~reltech/2009/09-06.pdf (states the conjecture as Conjecture 4.1)
3. Alberto Alexandre Assis Miranda and Cláudio Leonardo Lucchesi, On the Pfaffian number of graphs, Electronic Notes in Discrete Mathematics 35:145–150, 2009. DOI: 10.1016/j.endm.2009.11.025, https://doi.org/10.1016/j.endm.2009.11.025 (companion LAGOS'09 note)
4. Serguei Norine, Drawing 4-Pfaffian graphs on the torus, Combinatorica 29(1):109–119, 2009. DOI: 10.1007/s00493-009-2354-0, https://doi.org/10.1007/s00493-009-2354-0
5. Roberta Rasoviti Marques Costa Moço, Alberto Alexandre Assis Miranda and Cândida Nunes da Silva, The signature matrix for 6-Pfaffian graphs, Procedia Computer Science 195:298–305, 2021. DOI: 10.1016/j.procs.2021.11.037, https://doi.org/10.1016/j.procs.2021.11.037
6. Enrique Junchaya, Alberto Alexandre Assis Miranda and Cláudio L. Lucchesi, Lower Bounds for the Pfaffian Number of Graphs, arXiv:2603.00334, 2026. https://arxiv.org/abs/2603.00334
7. Priyanshu Pant and Ranveer Singh, Exponential Lower Bounds for the Pfaffian Number of Graphs, arXiv:2605.21077, 2026. https://arxiv.org/abs/2605.21077
8. Anna Galluccio and Martin Loebl, On the Theory of Pfaffian Orientations. I. Perfect Matchings and Permanents, The Electronic Journal of Combinatorics 6(1):R6, 1999. DOI: 10.37236/1438, https://doi.org/10.37236/1438
9. Glenn Tesler, Matchings in Graphs on Non-orientable Surfaces, Journal of Combinatorial Theory, Series B 78(2):198–231, 2000. DOI: 10.1006/jctb.1999.1941, https://doi.org/10.1006/jctb.1999.1941
10. P. W. Kasteleyn, The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice, Physica 27(12):1209–1225, 1961. DOI: 10.1016/0031-8914(61)90063-5, https://doi.org/10.1016/0031-8914(61)90063-5
11. P. W. Kasteleyn, Dimer Statistics and Phase Transitions, Journal of Mathematical Physics 4:287–293, 1963. DOI: 10.1063/1.1703953, https://doi.org/10.1063/1.1703953
12. L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8(2):189–201, 1979. DOI: 10.1016/0304-3975(79)90044-6, https://doi.org/10.1016/0304-3975(79)90044-6
13. Cláudio L. Lucchesi and U. S. R. Murty, Perfect Matchings: A Theory of Matching Covered Graphs, Algorithms and Computation in Mathematics 31, Springer, 2024. ISBN 978-3-031-47504-7, https://doi.org/10.1007/978-3-031-47504-7
14. Priyanshu Pant and Ranveer Singh, An Odd Pfaffian Number, arXiv:2609.22928, 2026. https://arxiv.org/abs/2609.22928