Lesson 4

The concept of biconnectivity generalizes naturally. We call an undirected graph vertex \(k\)-connected or simply \(k\)-connected if it has at least \(k+1\) vertices and remains connected after removing any \(t<k\) vertices. We call a graph edge \(k\)-connected if it remains connected after removing any \(t<k\) edges.

Later we will see that \(k\)-connectivity is directly related to the number of disjoint paths in the graph.