Cutset

Cutset is a term used in graph theory and reliability engineering to denote a set whose removal (or failure) changes the connectivity of a system. In graph-theoretic usage, a cutset can refer to either a vertex cut (a set of vertices whose removal increases the number of connected components) or an edge cut (a set of edges whose removal disconnects the graph). If no proper subset has this property, the cutset is called minimal. The smallest possible vertex cut has size equal to the graph's vertex-connectivity κ(G); the smallest edge cut has size equal to the edge-connectivity λ(G).

Edge cuts and vertex cuts are central to the study of network reliability and flow. The minimum cut problem seeks a cutset of smallest size; by the max-flow min-cut theorem, the value of a minimum s-t cut equals the maximum possible flow between two nodes in a corresponding network. In general, cutsets can be many; minimal cutsets provide irredundant failure scenarios.

Beyond pure graph theory, cutsets are used in reliability engineering and safety analysis. In system reliability, a cut set is a set of components whose simultaneous failure would cause system failure; minimal cut sets identify minimal combinations that cause failure. This concept underpins fault-tree analysis and risk assessment, and is applied in power grids, telecommunications, and software architectures.