Hojin Chu

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

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 $\delta(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 integ...