On k-con-critically n-connected graphs

摘要

We prove that every n-connected graph G of sufficiently large order contains a connected graph H on four vertices such that G - V(H) is (n - 3)-connected. This had been conjectured in Mader (High connectivity keeping sets in n-connected graphs, Combinatorica, to appear). Furthermore, we prove upper bounds for the order of all n-connected graphs of criticality 3, 4, and 5. (C) 2002 Elsevier Science (USA). [References: 7]