Independent Removable Edges in Cubic Bricks

• DOI: 10.37236/12540
• Publication Date: 2025-02-14T13:52:00Z
• Authors: Fuliang Lu; Jianguo Qian

An edge $e$ in a matching covered graph $G$ is removable if $G-e$ is matching covered, which was introduced by Lovász and Plummer in connection with ear decompositions of matching covered graphs. A brick is a non-bipartite matching covered graph without non-trivial tight cuts. The importance of bricks stems from the fact that they are building blocks of matching covered graphs. Improving Lovász's result, Carvalho et al. [Ear decompositions of matching covered graphs, Combinatorica, 19(2):151-174, 1999] showed that each brick other than $K_4$ and $\overline{C_6}$ has $\Delta-2$ removable edges, where $\Delta$ is the maximum degree of $G$. In this paper, we show that every cubic brick $G$ other than $K_4$ and $\overline{C_6}$ has a matching of size at least $|V(G)|/8$, each edge of which is removable in $G$.