So the question is to find an arbitrary set of edges that partition the graph?

In a K_n with equally weighted edges this problem seems easy: just take a random vertex and remove the edges connecting it to the neighbourhood. Any attempt at removing more vertices would yield in having to cut more edges, so the strategy removes the least amount of edges while partitioning the graph.

In a tree with equally weighted edges, this problem seems easy too: just remove a leaf. Every tree has leaves.

I can't think about graphs "between" the two creating a property that makes the the "I just take the vertex with the fewest adjacencies and remove it" strategy moot. Is it trivial with equally weighted edges? Is the problem only interesting when edges have differing weights?