edgecut

An edge cut of a graph is a set of edges whose removal increases the number of connected components of the graph. Equivalently, a cut set is the set of edges that cross a partition of the vertices into two nonempty parts; removing those crossing edges disconnects the graph.

The minimum size of an edge cut in a connected graph is called the edge connectivity, denoted λ(G). It measures how robustly connected the graph is to edge removals. If a graph has a low λ(G), a small number of edge removals can disconnect it. For example, a tree has λ(G) = 1, since removing any single edge splits the tree into two components. A cycle C_n with n > 2 has λ(G) = 2, and a complete graph K_n has λ(G) = n − 1. In general, λ(G) ≤ δ(G), the minimum degree of the graph.

In weighted graphs, edges have capacities or weights, and the minimum cut problem seeks a cut with minimum total crossing weight. The maximum flow and minimum cut theorems relate to this by showing that the smallest s–t cut capacity equals the maximum s–t flow. For undirected graphs, global minimum cuts can be found efficiently using Stoer–Wagner algorithms; for directed graphs, min s–t cuts are found via standard max-flow algorithms, and Gomory–Hu trees can summarize all pairwise minimum cuts.

Edge cuts have applications in network reliability, designer optimization, clustering, and circuit layout. They are closely related to vertex cuts (which remove vertices instead of edges) and to broader notions of graph connectivity.