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

  • Fuliang Lu
  • Xing Feng
  • Yan Wang


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_1, e_2\}$ such that $G-\{e_1,e_2\}$ 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_4$, 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.

Article Number