b-Invariant Edges in Essentially 4-Edge-Connected Near-Bipartite Cubic Bricks

A brick is a non-bipartite matching covered graph without non-trivial tight cuts. Bricks are building blocks of matching covered graphs. We say that an edge e in a brick G is b-invariant if $G-e$ is matching covered and a tight cut decomposition of $G-e$ contains exactly one brick. A 2-edge-connected cubic graph is essentially 4-edge-connected if it does not contain nontrivial 3-cuts. A brick G is near-bipartite if it has a pair of edges ₁, e₂\ such that G-₁,e₂\ is bipartite and matching covered. Kothari, de Carvalho, Lucchesi and Little proved that each essentially 4-edge-connected cubic non-near-bipartite brick G, distinct from the Petersen graph, has at least $|V(G)|$ b-invariant edges. Moreover, they made a conjecture: every essentially 4-edge-connected cubic near-bipartite brick G, distinct from K₄, has at least $|V(G)|/2$ b-invariant edges. We confirm the conjecture in this paper. Furthermore, all the essentially 4-edge-connected cubic near-bipartite bricks, the numbers of b-invariant edges of which attain the lower bound, are presented.