b‐Invariant Edges in Near‐Bipartite Bricks

ABSTRACT A connected graph is matching covered if it contains at least one edge and every edge lies in some perfect matching of . Lovász proved that every matching covered graph can be uniquely decomposed into a list of bricks (nonbipartite) and braces (bipartite) up to multiple edges; we let denote the number of bricks. An edge in a matching covered graph is removable if is also matching covered. Furthermore, a removable edge of a brick is ‐invariant if . Confirming a conjecture of Lovász, de Carvalho, Lucchesi, and Murty proved that every brick, distinct from , , and the Petersen graph, has a ‐invariant edge. A brick is near‐bipartite if it has a pair of edges such that is a bipartite matching covered graph. In this paper, strengthening the result of Zhang et al., we show that in a near‐bipartite brick with , every vertex of , except at most six vertices, is incident with at most two non‐‐invariant edges. Consequently, has at least ‐invariant edges, and all such graphs attaining this lower bound are presented.