Given an undirected graph $G=(V,E)$ with non-negative edge weights $c_{ij}$ for each $(i,j)\in E$ and a positive integer $M$, the problem asks to determine the minimum-weight set 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{and there exists a path from } i \text{ to } j \text{ in } 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 $F(S)=\binom{|V[S]|}{2}$. Therefore, the constraint imposed on the pairwise connectivity of $G[S]$ (i.e., $F(S)\geq M$) directly translates to the constraint on the number of nodes (i.e., $|V[S]|\geq k$ with $\binom{k}{2}\geq M$ and $\binom{k-1}{2}<M$).
However, I am currently struggling to prove the NP-hardness of the problem when the subgraph $G[S]$ is not required to be connected. While I believe the problem remains NP-hard, I am seeking a proof of it.
