Given an undirected graph $G=(V,E)$ with non-negative edge weights $c_{ij}$ for each $(i,j)\in E$ and an integer $M$, the problem asks to determine the minimum weight of edges $S\subseteq E$, such that the pairwise connectivity (the total number of node pairs connected by at least one path) in the edge-induced subgraph $G[S]:=(V[S],S)$ is at least $M$. Here, $V[S]:=\bigcup_{(i,j)\in S}\{i,j\}$.

Formally, for any edge subset $S\subseteq E$, let $$F(S):=|\left\{\{i,j\}\,:\,i,j\in V[S],~i\neq j,~\text{there exists a path from } i \text{ to } j \text{ in graph } G[S] \right\}|.$$ Then the problem can be formulated as $$\min_{S\subseteq E}\left\{\sum_{(i,j)\in S}c_{ij}\,:\,F(S)\geq M\right\}.$$

I have already proven that when the edge-induced subgraph $G[S]$ 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 this case, the subgraph $G[S]$ can be determined as a tree subgraph, and thus the constraint imposed on the pairwise connectivity of $G[S]$ directly translates to the constraint on the number of nodes in $G[S]$.

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.