Edge Cuts and Edge-Disjoint Paths

Two Ways to Describe Separation

To understand how a graph stays connected, it helps to ask two related questions. Which edges must be removed to break connectivity? And how many paths can travel between two vertices without reusing an edge? Edge cuts describe the first question; edge-disjoint paths describe the second. Their relationship gives a useful check on calculations, although the full equality between minimum cuts and maximum path packings is a later result.

Throughout, graphs are finite and simple. Deleting an edge \(e\) means removing \(e\) while keeping both its endpoints: the resulting graph is \(G-e\). Deleting a vertex \(v\) means removing \(v\) and every edge incident with it: the resulting graph is \(G-v\). These operations are different, even when they both affect connectivity.

For a connected graph, removing \(\partial_G(S)\) separates the vertices in \(S\) from those outside \(S\), so it is an edge cut. The vertices within either side need not remain connected to each other. An edge cut is not necessarily a set of every edge in the graph: it is a set whose removal creates at least two components. When we discuss a graph that is already disconnected, we will not call an edge set an edge cut just because its removal leaves the graph disconnected.

For distinct vertices \(s,t\), an \(s\)-\(t\) path has endpoints \(s,t\). Thus edge-disjoint \(s\)-\(t\) paths may share \(s\) and \(t\), as well as other vertices, but no edge. This differs from internally vertex-disjoint paths, which are not the subject here: paths in that kind of collection may share their endpoints but cannot share internal vertices.

A Basic Bound from Cuts

Proof. Each of the \(k\) paths must use at least one edge of \(F\). Otherwise that path would still be present in \(G-F\), contrary to the definition of an \(s\)-\(t\) edge-separating set. Choose one edge of \(F\) used by each path. No two paths can be assigned the same edge, since the paths are pairwise edge-disjoint. The choices therefore give \(k\) distinct edges in \(F\), so \(k\le |F|\). If \(k=0\), the inequality holds because \(|F|\ge0\). \(\square\)

This proposition is an upper bound, not a proof that a cut of size \(r\) always corresponds to exactly \(r\) edge-disjoint paths. It is often enough to check one direction: exhibit \(k\) edge-disjoint paths and a separating set of size \(k\), and the proposition shows that no larger collection of such paths exists.

Sharing Vertices Is Allowed

When checking edge-disjointness, compare edge sets, not just vertex sets. Paths can meet at an internal vertex and still be edge-disjoint. The next graph makes that distinction explicit.

Minimal Edge Cuts and Vertex Boundaries

An edge cut can contain edges that are unnecessary for disconnecting the graph. To make the distinction precise, call an edge cut \(F\) inclusion-minimal if no proper subset of \(F\) is an edge cut. Inclusion-minimal means that no edge can be discarded from the set while retaining its disconnection effect; it does not mean that \(F\) has the smallest possible size among all edge cuts.

Proof. First suppose \(F\) is an inclusion-minimal edge cut. Choose a connected component of \(G-F\), and let \(S\) be its vertex set. The set \(S\) is nonempty and proper because \(G-F\) is disconnected. Every edge of \(\partial_G(S)\) must belong to \(F\); an edge crossing from \(S\) to its complement that remained in \(G-F\) would join the chosen component to another vertex. Thus \(\partial_G(S)\subseteq F\). Removing \(\partial_G(S)\) disconnects \(G\), so \(\partial_G(S)\) is itself an edge cut. Inclusion-minimality of \(F\) gives \(F=\partial_G(S)\).

The subgraph \(G[S]\) is connected: \(S\) was chosen as the vertex set of a component of \(G-F\), and the edges within \(S\) were not removed, since \(F=\partial_G(S)\). Suppose \(G[V(G)\setminus S]\) were disconnected, and let \(A\) be the vertex set of one of its components. There are no edges from \(A\) to the rest of \(V(G)\setminus S\). Since \(G\) is connected, every edge from \(A\) to the rest of \(G\) must go to \(S\). Removing just the edges between \(A\) and \(S\), a subset of \(\partial_G(S)=F\), would disconnect \(A\) from the nonempty set \(S\). This subset is proper because \(G[V(G)\setminus S]\) has another component, which must have an edge to \(S\) by connectedness of \(G\). That contradicts inclusion-minimality. Hence \(G[V(G)\setminus S]\) is connected.

Conversely, suppose \(F=\partial_G(S)\), where \(S\) and its complement are nonempty and both induced subgraphs are connected. Removing all of \(F\) disconnects the two sides, so \(F\) is an edge cut. Let \(F'\) be any proper subset of \(F\). At least one edge of \(F\) remains in \(G-F'\). The two sides remain internally connected, and this remaining edge joins them, so \(G-F'\) is connected. Thus no proper subset of \(F\) is an edge cut, and \(F\) is inclusion-minimal. \(\square\)

Common Pitfalls

Wrong calculation: In the graph of the previous example, the paths \(s,a,x,c,t\) and \(s,b,x,d,t\) share \(x\), so they are not edge-disjoint. Correction: Write down the edges used by each path. The first uses \(\{sa,ax,xc,ct\}\); the second uses \(\{sb,bx,xd,dt\}\). Those edge sets have no edge in common. Sharing a vertex is allowed.

A second mistake is to treat every set that separates two particular vertices as a global edge cut. An \(s\)-\(t\) edge-separating set only needs to eliminate all \(s\)-\(t\) paths; it need not disconnect the rest of the graph. For example, in the diamond graph, \(\{sa,sb\}\) isolates \(s\), so it is both an \(s\)-\(t\) separating set and a global edge cut. In other graphs, separating specified vertices may leave the graph connected through other vertices, so check which property is required.

Finally, an inclusion-minimal cut is not automatically a minimum-size cut. Minimality says that no edge can be removed from that particular cut while keeping it a cut. A minimum-size cut is one with the least number of edges among all cuts under consideration. The theorem above characterizes inclusion-minimal cuts; it does not compare the sizes of different cuts.