Distribution of contractible edges in k-connected graphs

AbstractAn edge xy of a k-connected graph G is said to be k-contractible if the graph G · xy obtained from G by contracting xy is k-connected. We derive several new results on the distribution of k-contractible edges. Let G[Ek(G)] be subgraph of G induced by the set Ek(G) of k-contractible edges in G. We show that if G is a k-connected graph (k ≥ 2) which is triangle-free or has minimum degree at least ⌊3k2⌋, then G[Ek(G)] is 2-connected and spans G. Furthermore, if k ≥ 3, then G contains an induced cycle C such that every edge of C is k-contractible and G − V(C) is connected