We prove that if G is highly connected, then either G contains a non-separating connected subgraph of order three or else G contains a small obstruction for the above conclusion. More precisely, we prove that if G is k-connected (with k ≥ 2), then G contains either a connected subgraph of order three whose contraction results in a k-connected graph (i.e., keeps the connectivity) or a subdivision of whose order is at most 6.
展开▼
