Short note: Cutsets and cutvertices

• A cut vertex (articulation point) is a vertex whose removal, together with its edges, increases the number of connected components of the graph.
• A cut set (edge cut) is a set of edges whose removal disconnects the graph and which is minimal: no proper subset of it also disconnects the graph. A cut set with a single edge is a bridge.

Example:

   a
   | \          triangle abc with a pendant d attached to c
   b--c--d      edges: ab, ac, bc, cd

• c is a cut vertex (removing it leaves {a, b} and {d}).
• cd is a bridge, so {cd} is a cut set.
• {ac, bc} is also a cut set: removing both separates {a, b} from {c, d}, but removing either alone leaves the graph connected.

Connectivity: the vertex connectivity κ(G) is the minimum number of vertices whose removal disconnects G; the edge connectivity λ(G) is the size of the smallest cut set. κ(G) ≤ λ(G) ≤ minimum degree. A graph with no cut vertex (and at least 3 vertices) is 2-connected; Hamiltonian graphs have no cut vertex.

Use: finding the weak points of a network (a cut vertex or bridge is a single point of failure) and in max-flow min-cut.