degree sequence

Given a sequence of n numbers, d1 <= d2 <= d3 <= ... <= dn
find a graph with such degree or assert that it is not a valid sequence.

The hakimi algorithm constructs such a graph recursively. It finds a graph for
d2-1, d3-1, ... dk-1, d_k+1, ... d_n where k = d1 + 1, then add d1 to the graph connecting to each of d2 to d_k.

Obviously the degree sequence thus constructed is a valid graph, but why if the algorithm fails to find a graph, then no such graph exists.

The theorem shows that d_i sequence is a degree sequence iff the c_i sequence by removing d1 and subtract 1 from each of d2 to d_k is a degree sequence.

Sufficiency is easy, since we just add d1 to the c_i graph.

To see necessity, we first consider an easy case, when the d_i graph has d1 connected to d2 up to d_k and none beyond that. What if this is not true, then we can swap in some d_j with j > k with d_i for i in [2,k] while keeping all d_i intact. First because node 1 has deg = d1, it must have a neighbor beyond d_k, call it x, and in [2..k] there is a node that is not adjacent to d1, call it y. Now y has degree at least d1, and it is not connected to node[1], so y must have 2 or more neighbors in [k+1..n]. As a result there exists some node z != x such that (y,z) is an edge and we also have (1,x) is an edge. Then we swap the two edges by set (1,y) (x,z) to edges and remove (1,x), (y,z) from E. This does not change the d_i sequence yet we have one more neighbor of node[1] in [2..k]. So we will eventually have all node[1]'s neighbor in [2..k] and we are back to the easy case.