Connected, k-connected, bridge, cut vertex -- which term?
A graph can fail to hold together in several genuinely different ways; each has its own precise name.
Asking "can I get from anywhere to anywhere" is plain connectedness. Asking "how many vertices (or edges) have to fail before it splits" is vertex (or edge) connectivity -- \kappa(G) or \lambda(G). Asking about ONE specific vertex or edge whose removal alone disconnects the graph is a cut vertex or a bridge -- the \kappa=1/ \lambda=1 special case. In a digraph, "connected" splits again into strong and weak.
Undirected, yes/no
Undirected, how robust
Section
Cut vertices
Section
Bridges
\kappa(G) and \lambda(G) generalize cut-vertex/bridge from a single point of failure to a minimum-size failure set.
Theorem
Menger's Theorem
Vertex form. Let u and v be distinct, non-adjacent vertices of a graph G. The maximum number of pairwise internally vertex-disjoint u–v paths (paths sharing only their endpoints u and v) equals the minimum number of vertices whose removal disconnects u from v (a u–v vertex cut).
Edge form. For any two vertices u,v of G, the maximum number of pairwise edge-disjoint u–v paths equals the minimum number of edges whose removal disconnects u from v (a u–v edge cut).
Menger's theorem ties connectivity directly to the number of vertex- (or edge-) disjoint paths between two vertices.
Show proof
Both forms split into an easy inequality and a harder matching one; the edge form is proved here (the vertex form follows the same pattern, one level removed by splitting each vertex into an "in" and "out" copy joined by a unit-capacity edge).
Easy direction: max disjoint paths \le min cut. Let S be any u–v edge cut, and let P_1, \dots, P_k be any collection of pairwise edge-disjoint u–v paths. Every path P_i must use at least one edge of S (otherwise P_i would survive the removal of S, contradicting that S disconnects u from v). Since the paths are pairwise edge-disjoint, no single edge of S can be "used" by two different paths, so k \le |S|. Taking S to be a minimum cut gives (max disjoint paths) \le (min cut size).
Hard direction: min cut \le max disjoint paths. This direction is a direct consequence of the max-flow min-cut theorem. Build a flow network on the same vertex set as G, directing every edge both ways (or leaving G as-is if it is already directed) and giving every edge capacity 1, with source u and sink v. A flow of value k in this network that uses only integer edge-flows (guaranteed to exist at the maximum by the integrality of max-flow solutions on integer-capacity networks) decomposes into exactly k edge-disjoint u–v paths, since each edge carries at most 1 unit of flow and flow conservation forces every unit of flow entering a vertex (other than u,v) to leave along a different edge. By the max-flow min-cut theorem, this maximum flow value equals the capacity of a minimum u–v cut in the network — and because every edge has capacity 1, a minimum-capacity cut is exactly a minimum-size set of edges whose removal disconnects u from v. So \text{max edge-disjoint paths} = \text{max flow value} = \text{min cut capacity} = \text{min edge cut size}.
Combined with the easy direction, the two quantities are equal.
Directed
Section
Strong vs. weak connectivity
Section