What is the relationship between a local minimal cut and a global minimal cut?

82 Views Asked by At

An edge cut is a set of edges that, if removed from a connected graph, will disconnect the graph.

A minimal edge cut is an edge cut such that if any edge is put back in the graph, the graph will be reconnected.

A $(t,s)$-minimal edge cut of $G$ is a minimal edge cut that disconnect vertex $t$ from vertex $s$.

Clearly, a $(t,s)$-minimal edge cut is an edge-cut. But must it be a minimal cut of $G$?

That is say: Let $G$ be a graph. Is there a $(t,s)$-minimal edge cut that is not a minimal cut of $G$?

I prefer to find a graph $G$ and a $(t,s)$-minimal edge cut in $G$ that is not a minimal cut of $G$.

1

There are 1 best solutions below

2
On BEST ANSWER

This is true if you take a disconnected graph. For any $s,t $ vertices in the same connected component, adding back any edge of the cut will leave the graph disconnected.

However, if $G$ is connected, any minimal $(s,t)$ cut is a minimal cut. Suppose that adding back an edge of the $(s,t) $ cut leaves $G$ disconnected. Then $s $ and $t $ belongs to the same connected component, because they are no more disconnected. There must exist an edge of the cut that connects two connected components. This edge is a bridge. Suppose we add back only this edge. $s $ and $t $ are now connected, and there must exist a simple path between $s $ and $t $ that goes through this edge. We get a contradiction, because we would need to use this edge another time to get back to the original connected component.