\(N\) 頂点の単純無向グラフは辺を高々 \(\displaystyle\frac{N(N-1)}{2}\) 本しか持てないので，\(D > \displaystyle\frac{N-1}{2}\) のとき答えは No です． 逆に，\(D \le \displaystyle\frac{N-1}{2}\) のとき答えは Yes です． たとえば，各 \(i = 1, 2, \dots, N\) と各 \(k = 1, 2, \dots, D\) について，頂点 \(i\) と頂点 \((i + k)\)（ただし \(i + k > N\) のときは頂点 \((i + k - N)\) ）を結ぶ辺を張れば，条件を満たす単純無向グラフとなっています．

実装例 (C, 18 ms)

単純性

単純でない，すなわち自己ループまたは平行辺があると仮定して矛盾を導きます． このとき，ある \(i_1, i_2 \in \{1, 2, \dots, N\}\) と \(k_1, k_2 \in \{1, 2, \dots, D\}\) が存在して

\[i_1 + k_1 \equiv i_2, \quad i_2 + k_2 \equiv i_1 \quad (\mathrm{mod} ~N)\]

が成り立ちます．（自己ループの場合は \(i_1 = i_2\) であり，平行辺の場合は \(i_1 \neq i_2\) です．） 両辺を足して整理すると，

\[k_1 + k_2 \equiv 0 \quad (\mathrm{mod}~N)\]

が得られますが，これは

\[2 = 1 + 1 \le k_1 + k_2 \le D + D \le N - 1\]

と矛盾します．

誘導部分グラフの疎性

構成したグラフを \(G\) とし，各 \(k = 1, 2, \dots, D\) に対して，「頂点 \(i = 1, 2, \dots, N\) と頂点 \((i + k)\)（または頂点 \((i + k - N)\) ）を結ぶ辺のみを張って得られる \(G\) の部分グラフ」を \(G_k\) とします． \(G_k \ (k = 1, 2, \dots, D)\) は辺を共有せず，\(G\) はそれらの足し合わせで得られるので，任意の頂点部分集合 \(X\) について，\(X\) による \(G\) の誘導部分グラフの密度は，\(X\) による \(G_k\) の誘導部分グラフの密度の \(k\) に関する総和に等しいです．

任意の \(k\) について，\(G_k\) における各頂点の次数はちょうど \(2\) であり，そのようなグラフの各連結成分は閉路となります． このとき，任意の空でない頂点真部分集合 \(X\) について，\(X\) による \(G_k\) の誘導部分グラフの各連結成分は閉路または木であり，いずれに対しても \((頂点数) \ge (辺数)\) が成り立つため，その密度は \(1\) 以下です．

さらに，\(G_1\) は必ずハミルトン閉路（全頂点が連結な閉路）となります． したがって，任意の空でない頂点真部分集合 \(X\) について，\(X\) による \(G_1\) の誘導部分グラフは閉路を含まず，\((頂点数) > (辺数)\) が成り立つため，その密度は \(1\) 未満です．

以上より，任意の空でない頂点真部分集合 \(X\) について，\(X\) による \(G\) の誘導部分グラフの密度が \(D\) 未満であることが示せました．