It is known that a $\kappa$-connected graph of minimum degree at least $\lfloor 5 \kappa/4 \rfloor$ contains a $\kappa$-contractible edge, i.e. an edge whose contraction yields again a $\kappa$-connected graph. Here we prove the slightly stronger statement that a $\kappa$-connected graph for which the sum of the degrees of any two distinct vertices is at least $2 \lfloor 5 \kappa/4 \rfloor -1$ possesses a $\kappa$-contractible edge. The bound is sharp and remains valid and sharp if we look only at degree sums at pairs of vertices at distance one or two, provided that $\kappa \not=7$.
|Place of Publication||Enschede|
|Publisher||University of Twente, Department of Applied Mathematics|
|Publication status||Published - 1998|