Connectivity keeping edges in graphs with large minimum degree (Q933682): Difference between revisions

A classical result of \textit{G. Chartrand}, \textit{A. Kaugars}, and \textit{D.R. Lick} [Proc. Am. Math. Soc. 32, 63--68 (1972; Zbl 0211.27002)] says that every \(k\)-connected graph \(G\) with minimum degree at least \(3k/2\) contains a vertex \(v\) such that \(G-v\) is still \(k\)-connected. Inspired by this result, the authors prove that a \(k\)-connected graph \(G\) with minimum degree at least \(\lfloor 3k/2\rfloor+2\) contains an edge \(e=uv\) such that \(G-\{u,v\}\) is \(k\)-connected. Examples demonstrate that the given bound is best possible.