Cut in a connected graph is minimal iff corresponding partition induces connected subgraphs

60 Views Asked by At

This was claimed in Reinhard Diestel's Graph Theory textbook. This doesn't seem true at all to me. By cut I mean that if in a graph $G=(V,E)$, we have a vertex partition $\{V_1, V_2\}$, then the set of all edges crossing this partition is called a cut. By varying the (2 element) partitions, we get all the cuts of $G$. One direction is obvious: If in a graph $G = (V,E)$ we have a vertex partition $\{V_1, V_2\}$ and $V_1$ is disconnected, take one connected component of $V_1$ and remove it from $V_1$, adding it to $V_2$ and we get a vertex partition with a smaller cut. However, for the other direction, we have the following counterexample: Consider $G = K^n$, then if we have the partition $\{\{1,2\},\{3,\cdots,n\}\}$, we have $2n-4$ edges in our cut. If we have the partition $\{\{1,2,3\},\{4,5,\cdots,n\}\}$, then we have $3n-9$ edges in our cut, yet both partitions have connected subgraphs so how could they be minimal? Am I misunderstanding the definitions or is the statement just plain wrong?