Average degree and contractibility
Matthias Kriesell · Journal of Graph Theory · 2005
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