Suppose you are given an undirected graph $G$ with $n$ vertices and $k$ weighted edges.
Suppose that you'd like to find a set of $p$ groups using the following algorithm:
- Perform a minimum cut on $G$ and get $G1$ and $G2$.
- Continue to perform recursively minimum cut on the biggest of the two obtained subgraphs (i.e. on the one with more vertices) up until you end up with $p$ groups. For each cut, the sum of the edges' weight belonging to the cut, $P_c$, is calculated.
My question is: is it guaranteed that the sum $\sum_{cuts} P_c$ is the minimum possible?
Or, looking at it in another way, can I use another algorithm (other than minimum cut) that partitions my graph in $p$ subgraphs in order to get a lower $\sum_{cuts} P_c$ than the one obtained through the recursive application of minimum cut?
Your algorithm definitely will not always work.
Let $G$ be a graph consisting of 2 cliques $K_n$ and $K_m$ $n>m>p$ and an edge between the two cliques--each edge unit weight. Then the smallest cut that will partition $G$ into $p$ components is a cut between the cliques and then a cut of $K_m$ (the smaller of the two subgraphs and NOT the larger as you were proposing) that removes $p-1$ vertices.
If this example doesn't suit you, let $G$ be a clique $K_n$ on $n$ vertices and a path $P_m$ on $m$ vertices (disjoint from the clique), where one endpoint of $P_m$ is connected by an edge of unit weight and every other edge in $P_m$ has weight 2. (As before $n>m>p$)