各頂点を白と黒に塗り分け, 白の頂点は黒の頂点にのみつながるようにして, 黒の頂点は白の頂点のみにつながるようにする. こうすると, 同じ色の頂点同士の最短距離は \(2\) となる.

白の頂点の数を \(k\) とすると, 最短距離が \(2\) の頂点の組み合わせの数は,

\[\begin{align} {}_kC_2 + {}_{N-k}C_2 &= \frac{k(k-1)}{2} + \frac{(N-k)(N-k-1)}{2} \\ &= k^2 - Nk + \frac{N(N-1)}{2} \\ &= \left(k-\frac{N}{2}\right)^2 - \frac{N^2}{4} + \frac{N(N-1)}{2} \end{align}\]

となる.

これは \(k=1, N-1\) のときに最大となり, このときの組み合わせの数は \((N-1)(N-2)/2\) である. よって, \(K \gt (N-1)(N-2)/2\) ならばそのようなグラフは作れない.

\(K \leq (N-1)(N-2)/2\) のときのグラフの作り方は以下の通りである.

  • 完全グラフを作る. 組み合わせの数は \(0\) ある.
  • 頂点1から頂点2の辺を削除すると, 組み合わせの数が \(1\) 増える.
  • 同様に頂点1と頂点 \(i\) の辺を削除すると組み合わせの数が \(1\) 増える.
  • このまま頂点 \(i = N-1\) まで見て行く.
  • まだ足りないなら, 頂点2と頂点 \(i\) (\(i > 3\)) について見て行く.
  • 同様に頂点 \(N-1\) まで繰り返す.