A note on removable edges in near-bricks

Abstract

An edge $e$ of a matching covered graph $G$ is removable if $G-e$ is also matching covered. Carvalho, Lucchesi, and Murty showed that every brick $G$ different from $K_4$ and $\overline{C_6}$ has at least $\Delta-2$ removable edges, where $\Delta$ is the maximum degree of $G$. In this paper, we generalize the result to irreducible near-bricks, where a graph is irreducible if it contains no single ear of length three or more.

Keywords

• mathematics - combinatorics