Analysis: Counting Friends by Bruce Merry

The core part of the problem is simply to determine whether a set of vertex degrees corresponds to any graph. With an algorithm to do that, we can just try removing each of FJ's numbers in turn and checking whether the resulting set of numbers is viable.

While it is tempting to consider only parity, there are other cases where a list of degrees is infeasible. A simple case is one vertex with degree 0 and one vertex with degree N - 1: there both must and must not be an edge between them. We will clearly need a more robust test.

Let's take one vertex V with degree d(V) and try to assign its edges. Intuitively, we might aim to connect it to those vertices with higher degree, to try to avoid the problem case mentioned above. In fact, we can formalise this: if there is a valid assignment, then there is a valid assignment in which V is connected to the d(V) other vertices of highest degree. Let's consider any assignment in which this is not the case. Then V must be connected to some vertex A and not connected to some vertex B, with d(A) < d(B). Since B has more neighbors than A, it has a neighbor C that is not connected to A. Now we can replace edges V-A and B-C with edges V-B and A-C without affecting any degrees. This increases the degree sum of V's neighbors, so we can repeat this process a finite number of times until V is connected to the d(V) highest-degree vertices.

This now yields an algorithm for constructing the graph: take each vertex in turn, assign its edges as above, remove this vertex and its edges from the problem, and recursively check whether the remaining subproblem is solvable. With a little care, each iteration can be implemented in linear time (it is useful to store the counts as a frequency table and to work in decreasing order of degree), which makes the entire solution O(N³). With fancy data structures, the running time can be further reduced to O(N² log N).

As a further note, valid degree sequences can be characterized using a result known as the Erdos-Gallai Theorem. Using this, the running time can be reduced even further (e.g., to O(N²)).