Graph Theory37 sections · 1633 units
Open in Course

What is a Cut?

(Partitioning vertices)

A cut in a graph is a partition of vertices into two sets SS and TT where ST=VS \cup T = V and ST=S \cap T = \emptyset. Every vertex is in exactly one set. An edge (u,v)(u, v) crosses the cut if uSu \in S and vTv \in T (or vice versa). The cut separates the graph into two disconnected parts.

If you physically removed all crossing edges, the graph would split into two components. Think of it as drawing a line through the graph. Edges that cross the line are cut edges. The two sides cannot communicate without crossing this boundary.