Node Connectivity

The node connectivity between two nodes u and v is the number of nodes which have to be removed such that u and v are not connected by a path anymore. Link direction is not considered.

If u and v are connected by a direct link (u,v) then their node connectivity is the number of nodes in their connected component minus one.