A sharp extension of Halin's removable-edge theorem to matchings

Abstract

A subgraph $H$ of a $k$-connected graph $G$ is called \emph{$k$-removable} if $G-E(H)$ remains $k$-connected. Halin proved that every $k$-connected graph $G$ with $δ(G)\ge k+1$ has a $k$-removable edge. We extend this result from a single edge to matchings of any prescribed size by showing that, for positive integers $k$ and $m$, every $k$-connected graph $G$ with $δ(G)\ge\max\{k+1,2m-2\}$ contains a $k$-removable matching of size $m$, unless $G\cong K_{2m-1}$, or $(k,m)=(1,2)$ and $G$ is a cycle. This confirms a conjecture of Li, Zhou, Fujita, and Mao. The minimum degree bound is sharp, and both exceptions are unavoidable. Consequently, $\max\{k+1,2m-1\}$ is the sharp minimum degree threshold guaranteeing such a matching without exceptions. The proof combines a prescribed-set strengthening of Halin's removable-edge theorem with an extremal analysis of maximum $k$-removable matchings.

Disclosure

“≤ f (k, k + 1) ≤ k 2 for every k ≥ 2. In particular, we determine f (3, 4) = 3. Declaration of generative AI use. During the preparation of this work, the author used OpenAI’s GPT-5.6 Sol in order to gen- erate an initial proof of Lemma 3.5 and to provide grammatical and editorial suggestions on parts of the manuscript. After using this tool, the author independently verified the math- ematical arguments, reviewed and re”

PDF page 11

Classification

Drafting a complete proof for author revision

Multiplier

9

Verified

2026-08-23T05:07:28.070940Z

Structural counts