Vertex Connectivity

Vertex connectivity is the minimum number of vertices you must remove to disconnect the graph (or make it trivial if already small). This measures node-level resilience. You can compute it using max flow by splitting each vertex $v$ into $v_{in}$ and $v_{out}$ with an edge of capacity $1$ between them.

Then find minimum $s$-$t$ cuts for all pairs. The split vertices enforce that removing a vertex counts as $1$ unit. Vertex connectivity measures how many node failures the network can handle before becoming disconnected.