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

M. Kriesell

Research output: Book/ReportReportOther research output


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 languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 1998
Externally publishedYes


  • EWI-3283
  • MSC-05C40

Cite this