A generalization of Littleʼs Theorem on Pfaffian orientations

Little (1975) [12], showed that, in a certain sense, the only minimal non-Pfaffian bipartite matching covered graph is the brace K3,3. Using a stronger notion of minimality than the one used by Little, we show that every minimal non-Pfaffian brick G contains two disjoint odd cycles C1 and C2 such that the subgraph G−V(C1∪C2) has a perfect matching. This implies that the only minimal non-Pfaffian solid matching covered graph is the brace K3,3. (A matching covered graph G is solid if, for any two disjoint odd cycles C1 and C2 of G, the subgraph G−V(C1∪C2) has no perfect matching. Solid matching covered graphs constitute a natural generalization of the class of bipartite graphs, see Carvalho et al., 2004 [5].)