Course contentsShow
← Mathematics
Lesson 2663 of 3,12153. Graph TheoryFree lesson

Edge Connectivity

Define edge connectivity and k-edge-connected graphs; find minimum edge cuts and relate to vertex connectivity.

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.