多重集合 \(D = \{ d(i,j)\mid 1 \le i < j \le N\}\) について考えます。\(D\) の必要条件として、\(1\) の個数が \(M\) 以下が挙げられます。さて、この条件下において \(\sum_{e \in D} A_e\) を最小化しようとすると \(1\) を \(M\) 個入れ、残りを全て \(2\) で埋めたくなります。

実際にこの下界は達成可能で、ウニグラフに辺を \(M-(N-1)\) 本追加すると \(D\) が上記のようになることが確認できます。計算量は \(\mathrm{O}(N^2)\) です。