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

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 \[\delta(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 $\delta(G)\ge2k+1$ contains a $k$-removable matching of size $\bigl\lceil(\delta(G)+1)/2\bigr\rceil$, unless $\delta(G)$ is even and $G\cong K_{\delta(G)+1}$.

This verifies a conjecture of Li, Zhou, Fujita, and Mao in the range $\delta(G)\ge2k+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.