Vertex Connectivity

The connectivity (or vertex connectivity) K(G) of a connected graph G (other than a complete graph) is the minimum number of vertices whose removal disconnects G. When K(G) ≥ k, the graph is said to be k-connected (or k-vertex connected). When we remove a vertex, we must also remove the edges incident to it. As an example consider following graphs.

 

 

The above graph G can be disconnected by removal of single vertex (either b or c). The G has connectivity 1.

 

 

The above graph G can be disconnected by removal of single vertex (either c or d). The vertex c or d is a cut-vertex. The G has connectivity 1.

g46.gif

 

The above G can be disconnected by removing just one vertex i.e., vertex c. The vertex c is the cut-vertex. The G has connectivity 1.

 

 

The above G cannot be disconnected by removing a single vertex, but the removal of two non-adjacent vertices (such as b and c) disconnects it. The G has connectivity 2.