What do you mean by connectivity of graph?

Connectivity of a Graph

The connectivity of a graph refers to the minimum number of vertices that must be removed to disconnect the graph or reduce it to a single vertex. It is denoted by κ(G) and is a measure of the graph’s robustness against vertex deletions.

• If a graph remains connected after the removal of any single vertex, its connectivity is κ(G) ≥ 1.
• If no single vertex disconnects the graph, κ(G) = 0 (e.g., a tree).
• A graph with κ(G) ≥ k is called k-vertex-connected.

For example, a complete graph $K_n$ (where every pair of distinct vertices is connected by a unique edge) has κ(G) = n − 1, as removing any $n-2$ vertices still leaves the graph connected.

Connectivity ensures resilience in networks like the internet or social networks, where failure of a few nodes should not isolate parts of the system.