Edge Connectivity of a Graph

Edge connectivity of a graph refers to the minimum number of edges that must be removed to make a connected graph disconnected. This is denoted by $ λ(G) $.

In other words, it's the fewest number of edges you need to remove to ensure that at least one pair of vertices can no longer be connected by any path, thereby splitting the graph into two or more disconnected components.

Edge connectivity reflects how resilient a graph is to the removal of edges.

It indicates the number of edges that must be removed to disrupt the connectivity between the vertices of the graph.

Edge connectivity is crucial in many fields, such as communication networks, where it is important to ensure that the network remains connected even if some connections (edges) fail. A graph with higher edge connectivity is considered more robust than one with lower edge connectivity because it can tolerate the removal of more edges before becoming disconnected.

A graph is described as "k-edge-connected" if its edge connectivity is at least k, meaning that it takes a minimum of k edges to disconnect it, $ \lambda(G) \ge k $.

Example

Consider a graph consisting of a triangle (three vertices connected by three edges).

This is a connected graph because there is a path between every pair of vertices.

The edge connectivity $λ(G)$ of this graph is 2, because at least two edges must be removed to disconnect the graph, ensuring that at least one pair of vertices can no longer be connected by any path.

$$ λ(G) = 2 $$

For instance, you can disconnect the graph by removing edges (A,B) and (A,C) or edges (B,C) and (A,B).

Thus, the graph is 2-edge-connected, meaning that at least two edges must be removed to disconnect it.

This implies that the graph is both 1-edge-connected and 2-edge-connected, as it takes the removal of at least two edges to make it disconnected. However, it is not 3-edge-connected.