A simple undirected graph with \(N\) vertices can have at most \(\displaystyle\frac{N(N-1)}{2}\) edges, so the answer is No when \(D > \displaystyle\frac{N-1}{2}\). Conversely, when \(D \le \displaystyle\frac{N-1}{2}\), the answer is Yes. For example, for each \(i = 1, 2, \dots, N\) and each \(k = 1, 2, \dots, D\), connect vertex \(i\) and vertex \((i + k)\) (or vertex \((i + k - N)\) when \(i + k > N\)) with an edge, and you will get a simple undirected graph that satisfies the condition.

Sample Implementation (C, 18 ms)

Simplicity

Assume that the graph is not simple, i.e., it has a self-loop or multi-edges, and derive a contradiction. In this case, there are \(i_1, i_2 \in \{1, 2, \dots, N\}\) and \(k_1, k_2 \in \{1, 2, \dots, D\}\) such that:

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

(In the case of a self-loop, \(i_1 = i_2\), and in the case of multi-edges, \(i_1 \neq i_2\).) Adding both sides and rearranging, we get:

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

However, this contradicts

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

Sparsity of induced subgraphs

Let \(G\) be the constructed graph, and for each \(k = 1, 2, \dots, D\), let \(G_k\) be the subgraph of \(G\) obtained by connecting only the edges between vertex \(i = 1, 2, \dots, N\) and vertex \((i + k)\) (or vertex \((i + k - N)\)). \(G_k \ (k = 1, 2, \dots, D)\) do not share edges, and \(G\) is obtained by summing them up, so for any vertex subset \(X\), the density of the induced subgraph of \(G\) by \(X\) is equal to the sum over \(k\) of the densities of the induced subgraphs of \(G_k\) by \(X\).

For any \(k\), each vertex in \(G_k\) has a degree of exactly \(2\), and each connected component of such a graph is a cycle. In this case, for any non-empty proper vertex subset \(X\), each connected component of the induced subgraph of \(G_k\) by \(X\) is either a cycle or a tree, and in either case, \((\text{number of vertices}) \ge (\text{number of edges})\), so the density is at most \(1\).

Furthermore, \(G_1\) always forms a Hamiltonian cycle (a connected cycle containing all vertices). Therefore, for any non-empty proper vertex subset \(X\), the induced subgraph of \(G_1\) by \(X\) does not contain a cycle, and \((\text{number of vertices}) > (\text{number of edges})\), so the density is less than \(1\).

From the above, we have shown that for any non-empty proper vertex subset \(X\), the density of the induced subgraph of \(G\) by \(X\) is less than \(D\).

(Above is a modification of a translation by GPT-4.)