$b$-invariant edges in cubic near-bipartite brick

Fuliang Lu, Xing Feng, Yan Wang

Published 2019-05-17Version 1

A brick is a non-bipartite 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 it contains exactly one brick. Kothari, Carvalho, Lucchesi, and Little shown that each essentially 4-edge-connected cubic non-near-bipartite brick $G$, distinct from 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_4$, has at least $|V(G)|/2$ $b$-invariant edges. We confirm the conjecture in this paper. Furthermore, we characterized when equality holds.