# Chapter 47. Edge Connectivity

# Chapter 47. Edge Connectivity

Edge connectivity measures how strongly a graph remains connected when edges are removed.

In vertex connectivity, vertices were deleted. In edge connectivity, only edges are deleted while the vertices remain. The central question is the following:

How many edges must be removed before the graph becomes disconnected?

This leads to the notion of edge cuts and the edge connectivity of a graph.

Edge connectivity is important in transportation systems, communication networks, electrical circuits, and flow networks. If edges represent roads, cables, pipes, or communication links, then edge connectivity measures the number of link failures required to separate the network.

## 47.1 Edge Cuts

Let \(G=(V,E)\) be a graph.

A set of edges \(F \subseteq E\) is called an edge cut if deleting the edges in \(F\) disconnects the graph.

The graph obtained after deletion is denoted

$$
G - F.
$$

If \(G-F\) has more connected components than \(G\), then \(F\) is an edge cut.

An edge cut identifies a collection of links whose removal separates the graph into disconnected regions.

For example, consider the path graph

$$
v_1v_2v_3v_4.
$$

Removing the edge \(v_2v_3\) disconnects the graph into two smaller paths. Thus the single edge set

$$
\{v_2v_3\}
$$

is an edge cut.

By contrast, in a cycle graph, removing one edge leaves a path, which is still connected. Therefore no single edge of a cycle is an edge cut.

## 47.2 Bridges

An edge whose removal disconnects a graph is called a bridge, or cut edge.

Thus an edge \(e\) is a bridge if

$$
G - e
$$

is disconnected.

Bridges are the edge analogue of cut vertices.

In a tree, every edge is a bridge. Removing any edge splits the tree into two components.

In a cycle, no edge is a bridge. Removing one edge merely breaks the cycle into a path.

This illustrates an important principle:

Cycles create redundancy.

If an edge lies on a cycle, then there exists another route connecting its endpoints. Consequently, deleting that edge does not disconnect the graph.

This leads to a useful theorem.

## 47.3 Characterization of Bridges

An edge of a connected graph is a bridge if and only if it does not belong to any cycle.

This theorem gives a complete structural description of bridges.

Suppose an edge \(e=uv\) lies on a cycle. Then there is another path from \(u\) to \(v\) around the rest of the cycle. After deleting \(e\), this alternate route still exists, so the graph remains connected.

Conversely, suppose \(e\) is not contained in any cycle. Then there is no alternate path between its endpoints. Removing \(e\) destroys the only connection between the two sides of the graph, so the graph becomes disconnected.

Thus bridges occur precisely in regions where no redundancy exists.

## 47.4 Edge Connectivity

The edge connectivity of a graph \(G\), denoted

$$
\lambda(G),
$$

is the minimum number of edges whose deletion disconnects the graph.

For a disconnected graph,

$$
\lambda(G)=0.
$$

For a connected graph, \(\lambda(G)\ge1\).

If \(\lambda(G)=1\), then the graph contains a bridge.

If \(\lambda(G)\ge2\), then no single edge disconnects the graph.

More generally, if \(\lambda(G)\ge k\), then deleting fewer than \(k\) edges never disconnects the graph.

This number measures resistance to edge failures.

## 47.5 \(k\)-Edge-Connected Graphs

A graph is called \(k\)-edge-connected if

$$
\lambda(G)\ge k.
$$

Thus a graph is \(2\)-edge-connected when no single edge is a bridge.

The cycle graph \(C_n\) is \(2\)-edge-connected. Every pair of adjacent vertices lies on a cycle, so no edge deletion disconnects the graph.

The complete graph \(K_n\) is highly edge-connected. In fact,

$$
\lambda(K_n)=n-1.
$$

Every vertex has degree \(n-1\), and disconnecting the graph requires isolating some vertex by removing all incident edges.

## 47.6 Edge Connectivity and Degree

Let

$$
\delta(G)
$$

denote the minimum degree of a graph.

Then

$$
\lambda(G)\le\delta(G).
$$

To see why, choose a vertex \(v\) with minimum degree. Remove all edges incident to \(v\). Then \(v\) becomes isolated, so the graph becomes disconnected.

The number of removed edges equals

$$
\deg(v)=\delta(G).
$$

Therefore the smallest edge cut cannot be larger than the minimum degree.

Combining this with vertex connectivity gives the classical inequalities

$$
\kappa(G)\le\lambda(G)\le\delta(G).
$$

These inequalities relate three measures of graph robustness:

| Quantity | Meaning |
|---|---|
| \(\kappa(G)\) | Minimum vertex cut size |
| \(\lambda(G)\) | Minimum edge cut size |
| \(\delta(G)\) | Minimum degree |

The inequalities may be strict.

A graph can have high degree but still contain a small edge cut separating two dense regions joined by only a few edges.

## 47.7 Edge Cuts Defined by Vertex Partitions

Suppose

$$
V=A\cup B,
$$

where \(A\cap B=\emptyset\), and both \(A\) and \(B\) are nonempty.

The set of edges with one endpoint in \(A\) and one endpoint in \(B\) is called the cut determined by \((A,B)\).

It is denoted

$$
[A,B].
$$

The size of this cut is

$$
|[A,B]|.
$$

Removing all edges in \([A,B]\) disconnects the graph into two parts.

This viewpoint is fundamental because every edge cut arises from some partition of the vertex set.

For example, in the graph

$$
V=\{1,2,3,4\},
$$

suppose

$$
A=\{1,2\}, \qquad B=\{3,4\}.
$$

Then \([A,B]\) consists of all edges joining the left side to the right side.

Cuts defined by partitions are central in flow theory and optimization.

## 47.8 Local Edge Connectivity

Global edge connectivity measures the smallest edge cut anywhere in the graph.

There is also a local version.

For distinct vertices \(u\) and \(v\), the local edge connectivity

$$
\lambda(u,v)
$$

is the minimum number of edges whose removal separates \(u\) from \(v\).

This number depends on the chosen pair of vertices.

The global edge connectivity satisfies

$$
\lambda(G)=\min_{u\ne v}\lambda(u,v).
$$

Thus global connectivity records the weakest pairwise separation in the graph.

## 47.9 Edge-Disjoint Paths

Two paths are edge-disjoint if they share no edges.

Edge connectivity can be characterized by edge-disjoint paths in the same way that vertex connectivity is characterized by internally disjoint paths.

Menger's theorem for edges states:

The minimum number of edges separating two vertices equals the maximum number of edge-disjoint paths between them.

This theorem connects cuts and paths.

| Cut interpretation | Path interpretation |
|---|---|
| Remove edges to separate vertices | Find independent routes |
| Small edge cut | Few independent paths |
| Large edge connectivity | Many redundant routes |

For example, if two vertices are connected by three edge-disjoint paths, then at least three edge removals are required to separate them.

This theorem is one of the foundations of network flow theory.

## 47.10 Examples

### Example 1. Path Graph

For the path graph \(P_n\),

$$
\lambda(P_n)=1.
$$

Every edge is a bridge.

### Example 2. Cycle Graph

For the cycle graph \(C_n\),

$$
\lambda(C_n)=2.
$$

Removing one edge leaves a path, which remains connected. Removing two suitable edges disconnects the graph.

### Example 3. Complete Graph

For the complete graph \(K_n\),

$$
\lambda(K_n)=n-1.
$$

Disconnecting the graph requires isolating some vertex.

### Example 4. Complete Bipartite Graph

For the complete bipartite graph \(K_{m,n}\),

$$
\lambda(K_{m,n})=\min(m,n).
$$

The smaller part determines the weakest separation.

## 47.11 Edge Connectivity and Flows

Edge connectivity is closely related to network flows.

Suppose each edge has capacity one. Then the maximum amount of flow between two vertices equals the maximum number of edge-disjoint paths between them.

By the max-flow min-cut theorem, this equals the minimum edge cut separating the vertices.

Thus three quantities coincide:

| Quantity | Interpretation |
|---|---|
| Maximum flow | Transport capacity |
| Maximum edge-disjoint paths | Route redundancy |
| Minimum edge cut | Smallest separating failure set |

This equivalence is fundamental in combinatorial optimization.

## 47.12 Algorithms

Edge connectivity can be computed algorithmically.

### Detecting Bridges

Depth-first search can identify all bridges in linear time.

During DFS traversal, one computes discovery times and low values. An edge is a bridge precisely when no back edge bypasses it.

### Computing Minimum Cuts

Global minimum edge cuts can be found using flow algorithms or specialized cut algorithms such as Stoer-Wagner.

### Reliability Testing

In communication networks, edge connectivity provides a measure of fault tolerance.

A network with high edge connectivity can tolerate many link failures while remaining operational.

## 47.13 Edge Connectivity of Trees

Trees provide the simplest example of minimally connected graphs.

Every tree with at least two vertices satisfies

$$
\lambda(T)=1.
$$

Indeed, every edge of a tree is a bridge.

Trees therefore have the smallest possible positive edge connectivity.

This reflects the fact that a tree contains exactly one path between any two vertices. Removing one edge destroys that unique route.

## 47.14 Eulerian Graphs and Edge Connectivity

Eulerian graphs are naturally related to edge connectivity.

An Eulerian graph contains a closed walk using every edge exactly once.

Every connected Eulerian graph has no bridge unless the graph consists of a single cycle component. More generally, every edge of an Eulerian graph belongs to a cycle.

Thus Eulerian structure implies redundancy of edges.

However, high edge connectivity alone does not guarantee Eulerian structure, since Eulerian graphs also require even vertex degrees.

## 47.15 Applications

Edge connectivity appears in many applied settings.

| Application | Interpretation |
|---|---|
| Communication networks | Link failure tolerance |
| Transportation systems | Road or railway redundancy |
| Electrical networks | Circuit robustness |
| Internet routing | Alternate communication paths |
| Distributed systems | Reliability of connections |
| Infrastructure planning | Failure-resistant design |

In practice, edge failures are often easier to model than vertex failures. A cable may fail while routers remain operational. A road may close while cities still exist.

For this reason, edge connectivity is a central measure in network engineering.

## 47.16 Summary

Edge connectivity measures the minimum number of edges whose deletion disconnects a graph.

The main concepts are:

| Concept | Meaning |
|---|---|
| Edge cut | Set of edges disconnecting the graph |
| Bridge | Single edge whose deletion disconnects the graph |
| \(\lambda(G)\) | Minimum edge cut size |
| \(k\)-edge-connected | Remains connected after fewer than \(k\) edge deletions |
| Edge-disjoint paths | Independent routes sharing no edges |
| Menger's theorem | Minimum cuts equal maximum edge-disjoint paths |

Edge connectivity provides one of the basic measures of graph robustness. It links structural graph theory, path systems, network flows, and combinatorial optimization.