Does this algorithm for Graph Realization work? A sequence of integers $d_1, \dots, d_n$ is called graphical if there exists a simple graph $G$ with it as its degree sequence. Deciding if a sequence is graphical is called the Graph Realization Problem.
A theorem by Havel and Hakimi gives an algorithm to construct such a graph if it exists: it proceeds by repeatedly selecting a vertex of highest degree $v$ and connecting it to vertices of high degree until the degree of $v$ is depleted.
I want instead to consider the algorithm that, at every step, connects a vertex of highest degree with a single vertex of lowest nonzero degree.
Note that this algorithm, unlike the Havel-Hakimi one, does not select a vertex of the highest degree and connects it until its degree is depleted: a new vertex of highest degree is selected every time an edge is added.
For example, given the graphical degree sequence $2, 2, 2, 1, 1$, the algorithm proceeds as follows:
$$1,2,2,0,1\\0,1,2,0,1\\0,0,1,0,1\\0,0,0,0,0$$
which yields the simple path $P_5$ on five vertices (where I broke the ties selecting the leftmost highest or smallest).
Is there a counterexample for which this algorithm does not yield a graph realization?
NOTE: I expect the answer to be affirmative, since this algorithm won't ever connect two vertices of low degree unless it depleted everything else. Therefore, if any graph realization of a certain degree sequence must contain an edge between two vertices of low degree we're done, but I wasn't able to find such an example.
 A: There are some problems with your algorithm:
1)
It fails to distinguish solvable from unsolvable positions: If given a sequence such as nn it will happily go along adding edges between the two. This leads into
2)
Your algorithm doesn't produce simple graphs regardless of tiebreakers:
consider the sequence 64332222. this has a realization (just draw it). However, regardless of tiebreakers, your algorithm will always try to connect the first vertex to one of the 2s twice. This is one of the big upsides of havel-hakimi, by instantly depleting the degree of nodes when adding edges to them they don't run into the problem of multiedges.
If you were to restrict your algorithm to only connect unconnected edges it would likely produce valid realizations. However, that'd come at the cost of having to pass way more information along than the list of (unused) degree of each vertex. I think your algorithm will produce valid realizations because if you have a realization where there is an edge between vertices, say ab and cd and none between ac and bd then you may remove ab,cd and add ac,bd to produce another realization of the same sequence. In this way it should be possible to always avoid/force edges between vertexes of high and low degree.
