In graph theory, a minimum cut or min-cut of a graph is a cut (a partition of the vertices of a graph into two disjoint subsets) that is minimal in some metric. In the simplest unweighted min-cut problem, the goal is to minimize the number of edges connecting the two parts.

Variations of the minimum cut problem consider weighted graphs,