Average degree and contractibility

It is proved that for every number k there exists a number f ( k ) such that every finite k ‐connected graph of average degree exceeding f ( k ) contains an edge whose contraction yields again a k ‐connected graph. For the proof, tree orders on certain sets of smallest separating sets of the graph in question are constructed. This leads to new canonical tree decompositions as well. © 2005 Wiley Periodicals, Inc. J Graph Theory