Connectivity keeping paths in k-connected graphs

A result of G. Chartrand, A. Kaugars, and D. R. Lick [Proc Amer Math Soc 32 (1972), 63–68] says that every finite, k-connected graph G of minimum degree at least ⌊3k-2⌋ contains a vertex x such that G-x is still k-connected. We generalize this result by proving that every finite, k-connected graph G of minimum degree at least ⌊3k-2⌋+m-1 for a positive integer m contains a path P of length m-1 such that G-V(P) is still k-connected. This has been conjectured in a weaker form by S. Fujita and K. Kawarabayashi [J Combin Theory Ser B 98 (2008), 805–811]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 61–69, 2010.