I am working on the NP-hardness proof of a problem. Given an undirected graph with non-negative edge weights and an integer M, the problem asks to determine the minimum edge-weighted subgraph such that the pairwise connectivity (the total number of node pairs connected by at least one path) in the subgraph is at least M.

I have already proven that when the subgraph is required to be connected, the problem

"Given an undirected graph with non-negative edge weights and an integer M, find a connected subgraph with minimum edge weights such that the pairwise connectivity of the subgraph is at least M"

can be reduced from the "k-minimum spanning tree problem" (which is NP-hard). This is because that in the connected case, the subgraph can be selected as a tree subgraph, and thus the constraint imposed on the pairwise connectivity of the subgraph directly translates to the constraint on the number of nodes in the subgraph.

However, I am currently struggling to prove the NP-hardness of the problem when the subgraph is not required to be connected. While I believe the problem remains NP-hard, I am seeking a proof of it.