Prove that the deletion of edges of a minimum-edge cut of a connected
graph $G$ results in a disconnected graph with exactly two components.
(Note that a similar result is not true for a minimum vertex cut.)
Suppose that the deletion of edges of a minimum-edge cut of a
connected graph $G$ results in a disconnected graph with more than two components. Let $G_1, G_2, G_3,…G_k$ be the connected components obtained by removing minimum-edge cut of a connected graph. so, there exists $k$ edges required to make the graph connected. which contadict our assumption. Am I correct?
Best Answer
I think there is an important thing to add.
There exist $k-1$ (not $k$) edges from the original graph required to make it connected (if we take edges from the outside of original graph, the set being smaller doesn't make any contradiction), but each edge can have its endings in at most two of the connected components, and that's why adding one edge can change disconnectivity of at most two connected component only. So after adding one of these $k-1$ edges the disconnectivity of the graph cannot break, because we assumed that we have more than two connected components. Thus we obtained smaller (with quantity $k-2$) minimum-edge cut.
You can also go with graph with a vertex set $(G_{1}, G_{2}, \dots , G_{k})$ with empty edge set and a set of earlier deleted edges $A=(e_{1},e_{2},\dots,e_{k-1})$. For any connected graph it is true that $|E(G)|-1\geq |V(G)|$. Therefore for any set of edges smaller than $A$, the graph is disconnected.