Draw a Graph from a Given Degree Sequence I want to prove that this degree sequence $(5,5,5,2,2,2,1)$ isn't valid to draw a graph from it, the graph needs to be simple. I am looking for a Theroem or a way to contradict the assumption that we can make a graph from it.
My solution was the following, for the given nodes:degrees => $(A:5; B:5; C:3; D:2; E:2; F:2; G:1)$
Graph
Note that the vertex $C$ is the one that makes the contradiction, since we should have another 2 extra edges, but we can't add them to the previous nodes.
So my question is: Is there any theorem which I can use to prove this contradiction? Because I feel like my solution isn't enough.
 A: The Havel–Hakimi construction is as follows:
$$(5,[5,5,2,2,2],1)\to(4,[4,1,1,1],1)\to(3,1,0,0,0)$$
and the last degree sequence is not graphic since there is a degree-$3$ vertex but only one other non-isolated vertex. Hence the given degree sequence is not graphic.
A: Think about the number of edges between the first three vertices (with degrees $5,5,5$) and the last four (with degrees $2,2,2,1$).
On one hand, there must be at least $9$ such edges. Even if the first three vertices have all possible edges between themselves, that's only $2$ edges per vertex, with $3$ left over. So we have at least $3+3+3$ edges going from the first three to the last four.
On the other hand, there can be at most $7$ such edges: there are at most $2+2+2+1 = 7$ edges incident on any of the last four vertices.
This is a contradiction, so no graph can have this degree sequence.
(Side note: the Erdős–Gallai theorem tells us that whenever the degree sequence is not graphic, either it's because the sum of the degrees is odd, or else because a problem like the one above occurs.)
