The Norine–Thomas reduction conjecture for Pfaffian graphs

A graph is Pfaffian if it admits an orientation in which every nice even cycle (a cycle whose deletion leaves a perfect matching) is oddly oriented; Pfaffian orientations are the key to counting perfect matchings in polynomial time. Norine and Thomas (2008) conjectured a complete reduction-based characterization: a connected graph is Pfaffian if and only if it is not isomorphic to the twinplex and cannot be reduced to $K_{3,3}$ or the Petersen graph by a sequence of edge deletions, bicontractions, contractions of odd cycles, and compressions of types one, two, and three. The conjecture was designed to absorb the infinitely many minimally non-Pfaffian graphs discovered in the same paper, which rule out any finite forbidden matching-minor characterization. Partial confirmations are known for circulant graphs, Cayley graphs on Abelian and dihedral groups, and several Cartesian product families, but the conjecture remains open for general graphs. The problem asks for a proof or refutation of this conjecture in full generality.

Background

Counting the perfect matchings (dimer coverings) of a graph is #P-complete in general, but Kasteleyn showed that for planar graphs the count is computable in polynomial time: one orients the edges so that every 'nice' even cycle becomes oddly oriented, and a signed adjacency matrix then has a Pfaffian from which the number of perfect matchings is read off. Formally, a cycle $C$ of a graph $G$ is nice if $G-V(C)$ has a perfect matching; an orientation of $G$ is Pfaffian if every nice even cycle has an odd number of edges directed in each direction of traversal; and $G$ is Pfaffian if it admits such an orientation. Which graphs are Pfaffian is a central open problem of matching theory.

Three landmarks delimit what is known. Little proved that a bipartite graph is non-Pfaffian if and only if it contains an even subdivision of $K_{3,3}$ (the complete bipartite graph with three vertices in each part) as a nice subgraph — equivalently, $K_{3,3}$ occurs as a matching minor, where $H$ is a matching minor of $G$ if some even subdivision of $H$ (each edge replaced by an internally disjoint path of odd length) appears as a nice subgraph of $G$. Building on this, McCuaig, and independently Robertson, Seymour and Thomas (via a theorem on even directed circuits), gave polynomial-time algorithms to recognize Pfaffian bipartite graphs. For non-bipartite graphs the main landmark is Fischer and Little's characterization of near-bipartite graphs (1-extendable graphs, i.e. graphs in which every edge lies in some perfect matching, that become bipartite after deleting two suitable edges): such a graph is non-Pfaffian if and only if it has a matching minor isomorphic to $K_{3,3}$, the cubeplex, or the twinplex — the latter two being cubic near-bipartite bricks (a brick being a 3-connected graph in which deleting any two vertices leaves a graph with a perfect matching; bricks are the indecomposable non-bipartite blocks of graphs in which every edge lies in a perfect matching) on twelve vertices whose names are due to Norine and Thomas. Beyond these classes nothing comparable is known, and no polynomial-time algorithm is known for recognizing Pfaffian graphs in general.

A natural attack is through minimally non-Pfaffian graphs — non-Pfaffian graphs all of whose proper matching minors are Pfaffian. Little conjectured that $K_{3,3}$, the cubeplex, the twinplex and the Petersen graph (the 3-regular graph on ten vertices) are the only ones, which would have yielded a finite forbidden-minor characterization. Norine and Thomas disproved this by constructing, for every $k\ge 2$ and every matching $M$ of the odd cycle $C_{2k+1}$, a graph $G(k,M)$ that is minimally non-Pfaffian, so infinitely many obstructions exist. In the same paper they studied operations that preserve the Pfaffian property — deleting an edge; bicontraction, i.e. contracting the two edges incident with a vertex of degree two; contracting all edges of an odd cycle to a single vertex; and three local 'compression' operations that replace a specified central subgraph (a subgraph whose deletion leaves a perfect matching; the relevant ones span exactly ten vertices) by one or three new edges — and proposed a reduction-based characterization meant to absorb the infinitely many obstructions: Conjecture 4.3, the subject of this problem. In this system $K_{3,3}$ and the Petersen graph are the two non-Pfaffian base graphs, while the twinplex is non-Pfaffian yet admits no reduction to either base graph and therefore must be exempted explicitly.

Problem Statement

Prove or refute Conjecture 4.3 of Norine and Thomas (2008): a connected graph $G$ is Pfaffian if and only if $G$ is not isomorphic to the twinplex and $G$ cannot be reduced to $K_{3,3}$ or the Petersen graph by a sequence of the following operations, exactly as defined in that paper: edge deletions; bicontractions (contracting the two edges incident with a vertex of degree two); contractions of odd cycles; and compressions of types one, two, and three (the compressions are local replacement operations acting on a ten-vertex central subgraph, deleting four specified vertices of it and adding one new edge for types one and two and three new edges for type three, subject to the degree and centrality hypotheses stated in the paper). Here a reduction of $G$ to a graph $H$ means a finite sequence of these operations leading from $G$ to a graph isomorphic to $H$.

References

1. Serguei Norine and Robin Thomas, Minimally non-Pfaffian graphs, Journal of Combinatorial Theory, Series B 98 (2008) 1038–1055. DOI: 10.1016/j.jctb.2007.12.005. https://doi.org/10.1016/j.jctb.2007.12.005
2. Fuliang Lu and Lianzhu Zhang, The Pfaffian property of Cartesian products of graphs, Journal of Combinatorial Optimization 27 (2014) 530–540. DOI: 10.1007/s10878-012-9533-4. https://doi.org/10.1007/s10878-012-9533-4
3. Fuliang Lu and Lianzhu Zhang, A Conjecture of Norine and Thomas for Abelian Cayley Graphs, The Electronic Journal of Combinatorics 24(3) (2017) #P3.65. DOI: 10.37236/5456. https://doi.org/10.37236/5456
4. Fuliang Lu and Xiaodan Chen, The Pfaffian property of Cayley graphs on dihedral groups, Discrete Applied Mathematics 285 (2020) 642–649. DOI: 10.1016/j.dam.2020.07.006. https://doi.org/10.1016/j.dam.2020.07.006
5. Fuliang Lu, Lianzhu Zhang and Yan Wang, The Pfaffian property of circulant graphs, Discrete Applied Mathematics 181 (2015) 185–192. DOI: 10.1016/j.dam.2014.09.002. https://doi.org/10.1016/j.dam.2014.09.002
6. Wei Li and Yao Wang, Enumeration of Perfect Matchings of the Cartesian Products of Graphs, The Electronic Journal of Combinatorics 30(2) (2023) #P2.2. DOI: 10.37236/11141. https://doi.org/10.37236/11141
7. Wei Li, Yao Wang, Alishba Arshad and Wuyang Sun, A Characterization on Pfaffian Graphs of Cartesian Product $G\times C_{2n+1}$, Journal of Graph Theory 110 (2025) 33–40. DOI: 10.1002/jgt.23247. https://doi.org/10.1002/jgt.23247
8. C. H. C. Little, A characterization of convertible (0,1)-matrices, Journal of Combinatorial Theory, Series B 18 (1975) 187–208. DOI: 10.1016/0095-8956(75)90048-9. https://doi.org/10.1016/0095-8956(75)90048-9
9. Ilse Fischer and Charles H. C. Little, A Characterisation of Pfaffian Near Bipartite Graphs, Journal of Combinatorial Theory, Series B 82 (2001) 175–222. DOI: 10.1006/jctb.2000.2025. https://doi.org/10.1006/jctb.2000.2025
10. P. W. Kasteleyn, The statistics of dimers on a lattice, Physica 27 (1961) 1209–1225. DOI: 10.1016/0031-8914(61)90063-5. https://doi.org/10.1016/0031-8914(61)90063-5
11. N. Robertson, P. D. Seymour and R. Thomas, Permanents, Pfaffian Orientations, and Even Directed Circuits, Annals of Mathematics 150 (1999) 929–975. DOI: 10.2307/121059. https://doi.org/10.2307/121059
12. W. McCuaig, Pólya's Permanent Problem, The Electronic Journal of Combinatorics 11(1) (2004) #R79. DOI: 10.37236/1832. https://doi.org/10.37236/1832
13. Marcelo H. de Carvalho, Cláudio L. Lucchesi and U. S. R. Murty, A generalization of Little's Theorem on Pfaffian orientations, Journal of Combinatorial Theory, Series B 102 (2012) 1241–1266. DOI: 10.1016/j.jctb.2012.07.004. https://doi.org/10.1016/j.jctb.2012.07.004
14. Maximilian Gorsky, Raphael Steiner and Sebastian Wiederrecht, Strongly Pfaffian Graphs, in Extended Abstracts EuroComb 2021, Trends in Mathematics, vol. 14, Birkhäuser/Springer, Cham (2021) 267–272. DOI: 10.1007/978-3-030-83823-2_42. https://doi.org/10.1007/978-3-030-83823-2_42
15. Nishad Kothari, Orlando Lee, Cláudio L. Lucchesi and Cândida Nunes da Silva, Cubic graphs, S-minors and conformal minors, arXiv preprint (2026). DOI: 10.48550/arXiv.2606.04173. https://arxiv.org/abs/2606.04173