Edge Connectivity
You'll learn how edge connectivity measures how many edges you must remove to disconnect a graph, and how it relates to vertex connectivity.
The Core Idea
While vertex connectivity (from lesson 2662) measures the minimum number of vertices you must remove to disconnect a graph, edge connectivity focuses on edges.
The edge connectivity of a graph G, denoted κ'(G) (kappa-prime), is the minimum number of edges whose removal disconnects G or reduces it to a single vertex.
A graph is k-edge-connected if κ'(G) ≥ k. This means you need to remove at least k edges to disconnect it—the graph is resilient against edge failures.
Minimum Edge Cuts
An edge cut is a set of edges whose removal disconnects the graph. The smallest such set is called a minimum edge cut, and its size equals κ'(G).
Example: Consider a triangle (3-cycle). Removing any single edge still leaves two connected vertices. But removing any two edges disconnects it completely. Thus κ'(K₃) = 2.
Relationship to Vertex Connectivity
There's a fundamental inequality:
κ(G) ≤ κ'(G) ≤ δ(G)
where κ(G) is vertex connectivity and δ(G) is the minimum degree.
Why? Think of it this way: cutting edges is often "easier" than cutting vertices because removing a vertex eliminates all its incident edges. But you can't remove more edges than the minimum degree allows—a vertex with degree δ connects to only δ edges, so removing those δ edges isolates it.
Key Takeaway: Edge connectivity κ'(G) counts the minimum edges needed to disconnect a graph; a k-edge-connected graph survives removal of any k−1 edges, and edge connectivity lies between vertex connectivity and minimum degree.