Suppose that the distances to the vertices are fixed.

The graph is valid if and only if the edges satisfy the following:

• Every vertex with distance \(i\) is connected with at least one vertex with distance \((i-1)\).
• Edges between vertices with the same distances can be chosen freely.
• There are no edges between vertices whose distances differ by \(2\) or greater.

We will solve the problem with dynamic programming (DP) based on this discussion.

Let \(dp[i][j][k][l][s]\) be the number of graphs where the indices of the vertices distant by \(i\) or less have been determined, there are \(j\) edges between the vertices distant by \(i\) or less, and there are \(k\) vertices with even distances and \(l\) vertices with odd distances, among which \(s\) vertices have distance \(i\).

We will consider the transitions from \(i\) to \(i+1\) when \(i\) is even.

Fix the number of new vertices, \(x\). There are \(\binom{N-k-l}{x}\) ways to assign indices.

Next, notice the condition that

• every vertex with distance \(i\) is connected with at least one vertex with distance \(i-1\).

For each of \(x\) vertices, enumerate all possible number of vertices connected to those with distance \(i\). Finally, freely add edges between those with distance \(i+1\).

The number of such ways is solely dependent on the number of vertices with distance \(i\) and \(i+1\), so it can be precalculated as:

\(f(x,y,z)\): the number of ways to add edges between \(x\) vertices with distance \(i\) and \(y\) vertices with distance \(i+1\), so that there are a total of \(z\) edges between those with distance \(i\) and \(i+1\), and between those with distance \(i+1\).

Here, notice that the actual value of \(i\) is unnecessary for the actual transition. Only the parity of \(i\) matters, so the number of states can be reduced to \(O(N^5)\).

The writer’s solution costs \(O(N^3)\) time for a transition, for a total time complexity of \(O(N^8)\), but with a sufficiently small constant factor (\(\frac{1}{2}\) factor is everywhere) so it runs fast enough.