Let \(G(V,E,\gamma)\) be a connected graph and \(k > 0\) be a natural number. If after the removal of any subset of vertices \(X\subset V\) with \(|X| < k\) the graph \(G\) remains connected, then \(G\) is called \(k\)-connected.
In particular:
If \(G\) is \(1\)-connected, then it is connected.
If \(G\) is \(2\)-connected, it has no cutvertices. A \(2\)-connected graph is also called biconnected.
Algorithms: 1
Definitions: 2 3 4 5
Explanations: 6
Lemmas: 7 8 9
Proofs: 10 11 12 13 14 15 16
Propositions: 17 18 19 20
Theorems: 21