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

I have already proven that when the subgraph is required to be connected, the problem 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.