# A degree sum condition for the existence of a contractible edge in a $\kappa$-connected graph

M. Kriesell

Research output: Book/ReportReportOther research output

## Abstract

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$.
Original language Undefined Enschede University of Twente, Department of Applied Mathematics Published - 1998 Yes

• EWI-3283
• MSC-05C40