2026/07/20 by Hojin Chu, Ringi Kim, Boram Park
#math.CO
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 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) ≥ \begincases max\k+\lceil\tfrac m2\rceil, 2m\ if k≥ m,
k+m if k<m. \endcases As a consequence, every k-connected graph G with δ(G)≥2k+1 contains a k-removable matching of size \lceil(δ(G)+1)/2\rceil, unless δ(G) is even and G≅ Kδ(G)+1. This verifies a conjecture of Li, Zhou, Fujita, and Mao in the range δ(G)≥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.