But now I have the same question: since in the initial placement the algorithm checks whether all the degrees are less than maximum possible, how is this done? For my impossible graph, would it be that the first degree sequence would be 11, 11, ..., 11, and then it would throw away the whole degree sequence and generate new one (obviously it would again generate all 11, and would never be able to build the graph)? Or would it simply generate degree for the first vertex, and unless it is less than max-possible, it would keep attempting to change it? I think it does the later (that is why verbose says "added 1 vertex").

It does the latter.

If so, can we say that the initial degree sequence is drawn from a specified distribution?

Graphical degree sequences are *never* composed of i.i.d. degrees, since

they must fulfill the Erdős–Gallai inequality. For (uniformly) sparse

graphs, most sequences of i.i.d. degrees will fulfill it with high

probability, so we can say the degrees are approximately independent.

But as long as some degrees become large, this is no longer true.