Skip to content
Preprint

Removable matchings in $2$-connected graphs

Sep 2026 · 0 citations · 16 references
Mathematics

Abstract

A matching $M$ of a $2$-connected graph $G$ is removable if $G-M$ is $2$-connected, extending Halin's classical notion of a removable edge. We prove that for every integer $d\ge 5$, every $2$-connected graph $G$ with $\delta(G)\ge d$ and $|V(G)|\ge 2d$ has a removable $d$-matching. This is best possible, since the complete bipartite graph $K_{d,\,n-d}$ on $n\,(\ge 2d)$ vertices has no $(d+1)$-matching. Consequently, our result gives a complete answer, for every $d\ge 5$, to a question of Li, Zhou, Fujita, and Mao on the maximum size of a removable matching guaranteed by the minimum degree. The previously best known bound, due to Li, Zhou, Fujita, and Mao and to Chu, Kim, and Park, guaranteed a removable $(d-2)$-matching under the same assumptions. Our proof is based on an analysis of \emph{minimal non-removable matchings}, matchings that are not removable although all of their proper submatchings are.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.