For questions related to the vertex-connectivity or edge-connectivity of graphs or networks: the minimum number of vertices (respectively edges) that need to be deleted to disconnect the graph.
The connectivity of a graph is a measure of the graph's resilience as a network. The two most important measures of connectivity are:
- The vertex connectivity $\kappa(G)$ of a graph $G$: the minimum number of vertices that need to be deleted in order to disconnect the graph.
- The edge connectivity $\kappa'(G)$ of a graph $G$: the minimum number of edges that need to be deleted in order to disconnect the graph.
(As an exception to the usual definition, we let $\kappa(K_n) = n-1$ and $\kappa'(K_1) = 0$, since there is not such a minimum number for these graphs.)
There are also variants of these definitions for directed graphs, for weighted graphs, and for connectivity between two specific vertices.
A key result related to the connectivity of a graph is Menger's theorem.
