If $D=(d_1,d_2..)$ is graphic, then there is a simple graph with vertex labeling $V={v_1,v_2}$ such that $v_2,...v_{d_1 +1} \in N(v_1)$ Let $n \ge 2$ and $D=d_1,...d_n$ a graphic sequence.
Show: There is a simple graph G with vertices labeled $v_1, ... v_n$ such that $D$ is $G$'s degree sequence and $v_2,...v_{d_1 +1} \in N(v_1)$.
First I thought this is just very obvious since you can rename the vertices anyway you like so you might call the neighbours of your hightest degree vertex $v_2,...v_n$. (Because I first designed litte pictures of graphs which happend to have vertices with 'high' degrees as neighbours of the highest degree vertex.) But then the theorem didn't even seem right since I had a little picture of a graph that seemed to be a counterexample, I mean at least it wasn't completely obvious how to get the new desired graph out of the old one.
It was this:

Appearently the hightest degree vertex is on the left side, but it's not connected to the vertices with the next hightest degrees. I know that doesn't contradict the theorem but still I can't even figure out for this simple little example with degree sequence 42221111 which graph the theorem is speaking off.
Any hints and ideas are appreciated.
 A: Starting from any graph with $\deg(v_1) \ge \deg(v_2) \ge \dots \ge \deg(v_n)$, we can build a graph in which $v_1$ is adjacent to the $\deg(v_1)$ other vertices with the highest degree, one step at a time.
To do this, suppose that the graph is not in this form already. What does this mean? It means that at some point, the neighbors of $v_1$ "skip a step": $v_1$ is adjacent to $v_i$, but not to $v_{i-1}$.
Whenever this happens, we know that there must be some other vertex $v_j$ such that $v_{i-1} v_j$ is an edge, but $v_i v_j$ is not. That's because $\deg(v_{i-1}) \ge \deg(v_i)$, so $v_{i-1}$ has at least as many neighbors as $v_i$. We know $v_i$ has at least one neighbor that $v_{i-1}$ doesn't: that's $v_1$. To make up for that, $v_{i-1}$ must have at least one neighbor that $v_i$ doesn't.
Now, delete the edges $v_{i-1}v_j$ and $v_1 v_i$; in their place, put edges $v_i v_j$ and $v_1 v_{i-1}$. We get a new graph with the same degree sequence, and the neighbors of $v_1$ occur strictly earlier in the sequence $v_2, v_3, \dots, v_n$. (Formally, the sum of the set $\{i : v_1 v_i \in E\}$ decreases.)
Repeat this. Every time we do this, the graph gets closer to the form we want, until we are there.
Here is an illustration of one step of this process for the example you gave. $v_1, v_{i-1}, v_i, v_j$ are labeled; we add the edges in blue, and remove the edges scribbled out in red.

A: It won't, in general, be easy / possible to just relabel or slightly modify a graph with degree sequence $D$ to get one that has this neighborhood property you want. Your best bet is to just construct a graph from the ground up (and there is an easy method to do this).
Arrange your vertices $v_1, \dots, v_n$ in a line or circle, and label them, in order, by the degree (so here, going clockwise in a circle, we have $4, 2, 2, 2, 1, 1, 1, 1$) (see the picture).

Starting at the first vertex $v_1$ labelled $4$, draw $4$ edges to $v_2, v_3, v_4, v_5$ (red).
Then move on to $v_2$. From $v_2$, add edges in a clockwise order, until $deg(v_2) = d_2$, making sure to skip any vertices that already have high enough degree (orange).
Do the same for $v_3$ until $deg(v_3) = d_3$ (green). You'll notice that to get $v_3$ to work, we have to skip a vertex of degree $1$ that already has its desired degree.
Of course, if you get to a vertex and it already has enough neighbors, you just skip it. Do this until you add the last edge (blue), and you have the graph you want.
EDIT: This doesn't work in general. See MishaLavrov's answer for a correct algorithm.
