Minimum degree conditions for removable matchings in $k$-connected graphs

Abstract

In 1969, Halin proved that every $k$-connected graph $G$ with minimum degree at least $k+1$ contains an edge $e$ such that $G-e$ is $k$-connected. As an edge is a matching of size one, it is natural to ask whether Halin's result extends to matchings of larger size, a question recently investigated by Li, Zhou, Fujita, and Mao. A matching $M$ of a $k$-connected graph $G$ is called \emph{$k$-removable} if $G-M$ is $k$-connected. In this paper, we study minimum degree conditions that guarantee the existence of a $k$-removable matching of prescribed size. Specifically, we prove that for all positive integers $k$ and $m$, every $k$-connected graph $G$ with at least $2m$ vertices contains a $k$-removable matching of size $m$ if \[δ(G)\ \ge\ \begin{cases} \max\bigl\{k+\bigl\lceil\tfrac m2\bigr\rceil,\ 2m\bigr\} & \text{if } k\ge m,\\[2pt] k+m & \text{if } k<m. \end{cases}\] As a consequence, every $k$-connected graph $G$ with $\hat{I}´(G)\ge 2k+1$ contains a $k$-removable matching of size $\lceil (\hat{I}´(G)+1)/2\rceil$, unless $\hat{I}´(G)$ is even and $G\cong K_{\hat{I}´(G)+1}$. This verifies a conjecture of Li, Zhou, Fujita, and Mao in the range $\hat{I}´(G)\ge 2k+1$. Our main tool, of independent interest, is a strengthening of Halin's result producing a $k$-removable edge that avoids a prescribed set of vertices.