Cut (graph theory)

In graph theory, a **cut** is a way to partition the vertices of a graph into two disjoint subsets. More formally, given a graph \( G = (V, E) \), a cut is defined by a subset of the vertices \( S \subseteq V \). The cut divides the graph into two parts: one containing the vertices in \( S \) and the other containing the vertices in \( V \setminus S \).