A characterization of nonfeasible sets in matching covered graphs

Let G be a matching covered graph and let X ⊆ E ( G ) . Then X is called feasible if there exist two perfect matchings M 1 and M 2 in G such that ∣ M 1 ∩ X ∣ ≢ ∣ M 2 ∩ X ∣(mod 2 ) ; otherwise, it is nonfeasible. For any vertex v ∈ V ( G ) , the switching operation of X in v is defined as the symmetric difference of X and ∂ ( v ) , where ∂ ( v ) denotes the set of all edges in G incident with v . Two sets X 1 , X 2 ⊆ E ( G ) are switching‐equivalent if X 1 can be obtained from X 2 by a series of switching operations and vice visa. Lukot'ka and Rollová showed that if G is a regular bipartite graph, then X is nonfeasible if and only if X is switching‐equivalent to ∅ (as well as E ( G ) ). In this paper, we give a complete characterization of nonfeasible sets in matching covered graphs. We prove that if G is a matching covered graph and X is an arbitrary nonfeasible set of G , then X is switching‐equivalent to both ∅ and E ( G ) if and only if G is bipartite, and X is switching‐equivalent to either ∅ or E ( G ) (but not both) if and only if G is nonbipartite and G has an ear decomposition with exactly one double ear. We also show that for any two integers s and k with s ≥ 2 and k ≥ max { 3 , s } , there exist infinitely many k ‐regular simple graphs G of class 1 with arbitrarily large brick number, connectivity s and a nonfeasible set X such that X is not switching‐equivalent to either ∅ or E ( G ) . This gives negative answers to two problems proposed by Lukot'ka and Rollová and by He et al, respectively.