Graph Theory37 sections · 1633 units
Open in Course

Edge Connectivity

(Minimum edges to disconnect)

The edge connectivity of a graph is the minimum number of edges you must remove to disconnect the graph. It equals the capacity of the global minimum cut (when all edges have capacity 11). If the edge connectivity is kk, the graph remains connected after removing any k1k-1 edges, but becomes disconnected if you remove some set of kk edges.

Higher edge connectivity means a more reliable network.