Minimum amount of edges to remove to create k connected components in an undirected graph?

Question

How do I approach the problem: Minimum amount of edges to remove to create k connected components? The graph might already be a forest, though not necessarily one with k connected components, and may have cycles. It is unweighted and undirected.

Answer 1

If the original graph is a tree, then the removal of each edge will increase the number of connected components by 1. After removing k-1 edges, the graph will become a forest with k connected components.

Answer 2

• If the graph already has at least k components, then the answer is 0.
• If the graph is a tree, then the answer is k-1.
• If the graph is the complete graph with n nodes, then the answer is n-1 + n-2 + ... + n-k+1 = (n(n-1) - (n-k)(n-k+1))/2.
• Without assumption, the answer can be any number between 0 and (n(n-1) - (n-k)(n-k+1))/2.

Answer 3

we can use DSU(disjoint sets) kind of thing.