On non-planar, cycle-conformal graphs Maximilian Gorsky ​ Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea Clemens Kuske Technische Universität Berlin, Berlin, German Abstract A graph G G is called matching covered if all of its edges are contained in some perfect matching of G G . Furthermore, a cycle C ⊆ G C\subseteq G is called conformal if G − V ⁡ ( C ) G-V(C) has a perfect matching and G G itself is called cycle-conformal if all of its even cycles are conformal. Both matching covered graphs and conformal cycles play central roles in matching theory. After a string of results from various authors, focused mainly on bipartite, planar graphs and claw-free graphs, a complete characterisation of all planar, cycle-conformal graphs has recently been presented by Dalwadi, Pause, Diwan, and Kothari [DMTCS, 2025]. We continue this exploration further into the realm of non-planar graphs, giving a characterisation of matching covered, cycle-conformal graphs that are bipartite and cubic, and respectively, those that are bipartite and Pfaffian. The last class plays a fundamental role in matching theory, having important connections to the problem of counting perfect matchings, recognising graphs with even directed cycles, and computing the permanent of certain matrices efficiently. To prove our results, we break matching covered graphs down to their building blocks, the bipartite ones of which are called braces . The key to both characterisations are theorems that identify the braces in the respective classes. In particular, as our main results, we show that the cycle of length 4 is the only Pfaffian, cycle-conformal brace and we show that K 3 , 3 K_{3,3} is the only cubic, cycle-conformal brace. In both cases these theorems facilitate the characterisations of the much richer classes of associated matching covered graphs. We conjecture that for each integer ℓ ≥ 2 \ell\geq 2 the only ℓ \ell -regular, cycle-conformal brace is K ℓ , ℓ K_{\ell,\ell} . namesep= ,pairsep= and ,listsep=, ,lastsep= and ,tpairsep= and ,tlistsep=, ,tlastsep=, and ,notesep= ,rangesep= to ,type=book,Name-sg=Book,name-sg=book,Name-pl=Books,name-pl=books,type=part,Name-sg=Part,name-sg=part,Name-pl=Parts,name-pl=parts,type=chapter,Name-sg=Chapter,name-sg=chapter,Name-pl=Chapters,name-pl=chapters,type=section,Name-sg=Section,name-sg=section,Name-pl=Sections,name-pl=sections,type=paragraph,Name-sg=Paragraph,name-sg=paragraph,Name-pl=Paragraphs,name-pl=paragraphs,Name-sg-ab=Par.,name-sg-ab=par.,Name-pl-ab=Par.,name-pl-ab=par.,type=appendix,Name-sg=Appendix,name-sg=appendix,Name-pl=Appendices,name-pl=appendices,type=page,Name-sg=Page,name-sg=page,Name-pl=Pages,name-pl=pages,rangesep=–,rangetopair=false,type=line,Name-sg=Line,name-sg=line,Name-pl=Lines,name-pl=lines,type=figure,Name-sg=Figure,name-sg=figure,Name-pl=Figures,name-pl=figures,Name-sg-ab=Fig.,name-sg-ab=fig.,Name-pl-ab=Figs.,name-pl-ab=figs.,type=table,Name-sg=Table,name-sg=table,Name-pl=Tables,name-pl=tables,type=item,Name-sg=Item,name-sg=item,Name-pl=Items,name-pl=items,type=footnote,Name-sg=Footnote,name-sg=footnote,Name-pl=Footnotes,name-pl=footnotes,type=endnote,Name-sg=Note,name-sg=note,Name-pl=Notes,name-pl=notes,type=note,Name-sg=Note,name-sg=note,Name-pl=Notes,name-pl=notes,type=equation,Name-sg=Equation,name-sg=equation,Name-pl=Equations,name-pl=equations,Name-sg-ab=Eq.,name-sg-ab=eq.,Name-pl-ab=Eqs.,name-pl-ab=eqs.,refbounds-first-sg=,(,),,refbounds=(,,,),type=theorem,Name-sg=Theorem,name-sg=theorem,Name-pl=Theorems,name-pl=theorems,type=lemma,Name-sg=Lemma,name-sg=lemma,Name-pl=Lemmas,name-pl=lemmas,type=corollary,Name-sg=Corollary,name-sg=corollary,Name-pl=Corollaries,name-pl=corollaries,type=proposition,Name-sg=Proposition,name-sg=proposition,Name-pl=Propositions,name-pl=propositions,type=definition,Name-sg=Definition,name-sg=definition,Name-pl=Definitions,name-pl=definitions,type=proof,Name-sg=Proof,name-sg=proof,Name-pl=Proofs,name-pl=proofs,type=result,Name-sg=Result,name-sg=result,Name-pl=Results,name-pl=results,type=remark,Name-sg=Remark,name-sg=remark,Name-pl=Remarks,name-pl=remarks,type=example,Name-sg=Example,name-sg=example,Name-pl=Examples,name-pl=examples,type=algorithm,Name-sg=Algorithm,name-sg=algorithm,Name-pl=Algorithms,name-pl=algorithms,type=listing,Name-sg=Listing,name-sg=listing,Name-pl=Listings,name-pl=listings,type=exercise,Name-sg=Exercise,name-sg=exercise,Name-pl=Exercises,name-pl=exercises,type=solution,Name-sg=Solution,name-sg=solution,Name-pl=Solutions,name-pl=solutions 1 Introduction A core part of structural matching theory is the study of cycles whose deletion leaves us with a graph with a perfect matching. Such cycles are called conformal . These cycles, and more generally subgraphs with this property, play a key role in structural matching theory [ 10 , 9 , 11 , 8 ] , ear-decompositions (see [ 36 , 23 ] ), the resolution of Pólya’s Permanent Problem 1 1 1 Pólya asked for the conditions under which, given a 0-1-matrix A , one could flip some of the 1s in A to -1 s to obtain the matrix B such that the permanent of A equals the determinant of B . This problem has numerous surprising connections to areas outside of linear algebra (see [ 35 , 28 ] ). [ 35 , 28 ] , and extensions of these results [ 7 , 30 , 12 , 13 ] . Arising naturally from the significance of this property to the matching structure of graphs, one may therefore wonder which graphs have the property that all of their cycles are conformal. However, any graph with a perfect matching that has odd cycles cannot have this property. Thus, as it is natural in this context to study graphs with perfect matchings, we concentrate on the case in which we ask for all even cycles to be conformal. We call a graph cycle-conformal if it has a perfect matching and all of its even cycles are conformal. 2 2 2 This property has been studied under several names. We discuss our naming choice at the end of the introduction. Within the class of cycle-conformal graphs, we may further restrict ourselves to the study of matching covered graphs, that is graphs with at least four vertices in which all edges are contained in a perfect matching of the graph. These graphs are another central feature of matching theory. We justify this restriction later on by showing that the characterisation of cycle-conformal graphs can easily be reduced to matching covered graphs (see ?? ). The class of matching covered, cycle-conformal graphs first popped up explicitly when Guo and Zhang gave a characterisation of the planar, bipartite graphs in this class [ 14 ] , a result which has been replicated independently several times [ 46 , 31 , 19 ] (see also [ 17 ] ). Concerning matching covered, cycle-conformal, claw-free graphs, a characterisation of the planar graphs in this class was first given by Peng and Wang [ 32 ] and a full characterisation was achieved by Zhang, Wang, Yuan, Ng, and Cheng [ 47 ] . Most recently Dalwadi, Pause, Diwan, and Kothari significantly advanced the topic by providing a full characterisation of planar, matching covered, cycle-conformal graphs [ 3 ] . In general, the characterisations mentioned above are a bit too involved to state explicitly. Once we restrict ourselves to the building blocks that make up matching covered graphs, there are however some notable patterns to observe. Here two classes of graphs emerge from the tight cut decomposition procedure due to Lovász [ 24 ] , introduced in detail later on in this introduction, that is of central importance in matching theory. The graphs in the first class are called bricks , which are nonbipartite, 3-connected graphs in which the deletion of any pair of vertices yields a graph with a perfect matching. The second class consists of braces , which are 2-connected, bipartite graphs in which any matching of size at most two can be extended to a perfect matching of the graph. Thus the cycle of length 4, denoted as C_{4} , is a brace. Our results. We first note the following result, which we deem to be folklore as it immediately follows from the characterisation in [ 14 ] , but is first mentioned explicitly in [ 3 ] . Proposition 1.1 (folklore) . C_{4} is the unique planar, cycle-conformal brace. 3 3 3 [ 3 ] also consider K_{2} to be a cycle-conformal brace due to a difference in their definition of what constitutes a brace. In fact, the only effect of this difference is whether or not K_{2} is considered a brace. We will provide our own proof of this result later on (see ?? ). The argument for this is fairly simple, making use of some very convenient topological properties of the planar setting (as do all other proofs of this that we are aware of). Clearly, once we leave the realm of planar graphs, we can no longer directly rely on these methods. Our first main contribution is a generalisation of this result to Pfaffian graphs , whose definition we postpone to ?? . Bipartite Pfaffian graphs are the central class that needed to be characterised to resolve Pólya’s Permanent Problem [ 35 , 28 ] and they are notable for allowing the efficient computation of their number of perfect matchings, a problem which is otherwise known to be \#\mathsf{P} 4 4 4 A complexity class for counting problems that is associated with the set of decision problems in \mathsf{NP} . -complete [ 37 ] . Pfaffian graphs thus form an important fundamental class in matching theory. Kasteleyn laid the groundwork for the study of these graphs by showing that all planar graphs are Pfaffian [ 16 ] . Thus ?? is properly generalised by our first main result. Theorem 1.2 . C_{4} is the unique Pfaffian, cycle-conformal brace. In our proof of this result, we use the characterisation of Pfaffian braces due to Robertson, Seymour, and Thomas [ 35 ] , and McCuaig [ 28 ] to extend some convenient properties of planar graphs to Pfaffian graphs. In light of ?? , one might suspect that there are only few cycle-conformal braces in total. This is easily seen to be false however, as for all t\in\mathbb{N} with t\geq 2 , it is easy to prove that K_{t,t} is a cycle-conformal brace and similarly, K_{2t} is a cycle-conformal brick. Furthermore, there even exist infinitely many planar, cubic, cycle-conformal bricks [ 3 ] . This trend continues in non-planar, cubic, cycle-conformal bricks, as we remark upon in ?? . However, we provide the following result for cubic braces which starkly contrasts the situation for bricks. Theorem 1.3 . The only cubic, cycle-conformal brace is K_{3,3} . Unlike with ?? , the proof of this theorem is completely detached from the methods used for planar graphs. Instead we first invest significant effort to show that we can find a special K_{3,3} -subdivision in any cubic, cycle-conformal brace and then show that there is no way to build any cycle-conformal graph around this special subgraph. This remarkable difference in the richness of the class of cubic, cycle-conformal bricks and cubic, cycle-conformal braces motivated us to search for more cycle-conformal braces. However, we could not find any aside from the aforementioned trivial examples furnished by the complete bipartite graphs. In light of this we pose the following conjecture, for which ?? resolves the case \ell=3 and C_{4}=K_{2,2} trivially verifies the case \ell=2 . Conjecture 1.4 . For each integer \ell\geq 2 , the only \ell -regular, cycle-conformal brace is K_{\ell,\ell} . In fact, we pose the following stronger conjecture, which would imply ?? . Due to being considerably more general than ?? , our confidence that this second conjecture holds is notably lesser. Conjecture 1.5 . Each cycle-conformal brace is a complete bipartite graph. Returning to the discussion of our results, we must mention that the restriction of our efforts to braces is not beyond reproach. To explain this, we will now formally introduce the necessary definitions to outline the tight cut decomposition due to Lovász. In a graph G with a set X\subseteq V(G) , we denote by \partial(X)\subseteq E(G) the cut (around X ) , that is the collection of all edges incident with exactly one vertex in X . By \overline{X} we denote the set V(G)\setminus X . If G is matching covered, a cut \partial(X) is called tight if for all perfect matchings M of G we have |M\cap\partial(X)|=1 . Such a tight cut is called trivial if we have |X|=1 or |\overline{X}|=1 . Given a tight cut \partial(X) in G , we denote by G[X\mapsto c] the graph that results from contracting X into a single vertex c and deleting any resulting loops or parallel edges. Analogously, G[\overline{X}\mapsto c] is the graph that results from contracting \overline{X} instead. Both G[X\mapsto c] and G[\overline{X}\mapsto c] are called tight cut contractions of G . As Lovász proved [ 24 ] , the result of repeatedly taking tight cut contractions starting with a matching covered graph G is a unique list of graphs that do not have non-trivial tight cuts, independent of which particular tight cuts were chosen during the procedure. In particular, it is possible to carry out this process in polynomial time [ 24 ] . If a matching covered graph does not have non-trivial tight cuts it is called a brace , if it is bipartite, and a brick , if it is non-bipartite, which gives equivalent definitions of the two classes we introduced earlier [ 34 , 24 ] . While many problems in matching theory can be safely reduced to bricks and braces – as several properties are preserved by the operation of taking tight cut contractions (see for example [ 38 , 12 , 13 ] and ?? ) – this is not entirely true for the property of being cycle-conformal. However, one of the two directions does hold. Proposition 1.6 (Dalwadi, Pause, Diwan, and Kothari [ 3 ] ) . Let G be a matching covered graph with a tight cut \partial(X) and let G_{1},G_{2} be the two tight cut contractions corresponding to \partial(X) . Then if G is cycle-conformal, so are G_{1} and G_{2} . That a matching covered, cycle-conformal graph may have non-cycle-conformal bricks or braces was already pointed out in [ 3 ] . This negative result can be extended, as such graphs exist even if all involved graphs are bipartite and planar (see ?? ). Contrasting this, we show that cubic, matching covered, bipartite graphs are indeed closed under taking tight cut contractions. Lemma 1.7 . A cubic, matching covered, bipartite graph is cycle-conformal if and only if its braces are cycle-conformal. Figure 1 : A matching covered, planar, bipartite graph whose braces are all isomorphic to C_{4} . In the graph in the middle a non-conformal even cycle is indicated in red. On the right a tight cut is indicated such that both tight cut contractions corresponding to it are cycle-conformal. The counterexample from [ 3 ] we discussed above easily demonstrates that the condition of being bipartite is necessary in the above statement. Combined with ?? , the above lemma allows us to provide the following characterisation. Theorem 1.8 . A cubic, bipartite, matching covered graph is cycle-conformal if and only if all of its braces are K_{3,3} . Furthermore, the fact that tight cut contractions do not preserve being cycle-conformal tells us that ?? is not enough to itself characterise the Pfaffian, bipartite, cycle-conformal graphs. However, with a bit of work this can be overcome, allowing us to extend ?? to a characterisation of matching covered, Pfaffian, bipartite, cycle-conformal graphs. Theorem 1.9 . Any matching covered, bipartite, cycle-conformal graph is Pfaffian if and only if it is planar. For the convenience of the reader, we provide one of the characterisations of matching covered, bipartite, cycle-conformal, planar graphs at the end of ?? (see ?? in particular). Related work. One may also be interested in the number of perfect matchings that remain after the deletion of an even cycle. If one demands that after the deletion of any even cycle the resulting graph has at most one perfect matching, this gives a definition for the class known as perfect matching compact graphs (as pointed out in [ 42 ] ). These graphs have been studied extensively over the years [ 40 , 21 , 41 , 39 , 5 , 51 , 49 ] . The problem of recognising perfect matching compact graphs is known to be in co- \mathsf{NP} but not known to be in \mathsf{NP} (see [ 5 ] ), a situation which mirrors the state of the art for cycle-conformal graphs (see [ 3 ] ). Recently graphs in which the deletion of any cycle results in a unique perfect matching have started to be considered as well [ 42 , 48 , 50 ] and clearly any such graph is also cycle-conformal. A specialised version of this is found in the study of forcing faces in bipartite planar graphs (see [ 1 , 2 ] ). A note on terminology. There exist several other names in the literature for cycle-conformal graphs. They are also known as cycle-nice (see [ 47 ] ), 1-cycle-resonant (see [ 17 ] ), or cycle-extendable (see [ 3 ] ) graphs. Our choice to introduce yet another name for this class is grounded in an attempt to give this class a non-generic, appropriate, and distinct name. Terms like good and nice are often used to generically describe a property of a graph in a variety of unrelated context and are thus not specific enough. The property of being 1-cycle-resonant only coincides with being cycle-conformal in the context of bipartite graphs, making it inappropriate for the class as a whole. Finally, the term cycle-extendable does give a great description of what we expect our cycles to do, 5 5 5 Any perfect matching of an even cycle in a cycle-conformal graph G can be extended to a perfect matching of G . but there already exists a well-studied class of graphs that are called cycle extendable (see the line of research based on the concepts in [ 15 ] ). We believe that the name cycle-conformal is non-generic and accurately reflects that we want each (even) cycle to be conformal. Furthermore, a search for the term “cycle-conformal” did not yield any other related graph-theoretic literature in conflict with this class. We also note that the term conformal itself has appeared in different guises, having been called well-fitted [ 28 ] , nice [ 24 ] , and central [ 35 ] . Here we base our decision on the fact that the term conformal has been the de facto consensus established throughout the most prominent publications in matching theory over the last two decades (see [ 45 , 25 ] for reference). Structure of the paper. We start by providing the preliminaries necessary for our results in ?? . This is followed by the proof of ?? in ?? and a study of tight cuts in ?? , which includes the proofs of ?? and ?? . In ?? we provide the proof of ?? from which ?? then follows with ease. We conclude our paper with a discussion of non-bipartite cycle-conformal graphs and possible directions for future research in ?? . 2 Preliminaries The graphs in this paper are loopless and do not possess multiple edges. We generally adopt our notation for graphs from [ 6 ] , except where otherwise noted. For example, we denote the complete graph on t vertices as K_{t} . We will consider bipartite graphs throughout much of this article. A graph G is called bipartite if its vertex set can be partitioned into two disjoint sets A,B such that all edges of G have one end in A and the other in B . We call A and B the colour classes of G and will often refer to G having black and white vertices, which refers to containment of the vertices in these two sets. These colours will also be used to indicate the colour classes of a bipartite graph in our figures. We denote the complete bipartite graphs with s white vertices and t black vertices as K_{s,t} . If t\geq 3 , we let C_{t} denote the cycle on t vertices. We will often call a cycle of length 4 a 4-cycle . Paths, Separators, and Subdivisions. Let G be a graph and let k be a positive integer. We call a set S\subseteq V(G) a separator (in G ) if G-S is non-empty and not connected. If S=\{v\} , we also call v a cut-vertex and in general, if |S|=k , we call S a k -separator (in G ) . The graph G is called k -connected if it contains at least k+1 vertices and there does not exist a k^{\prime} -separator in G with k^{\prime}