Havel Hakimi: Is this sequence graphical? I start studying graphs and I'm not sure if I'm using this theorem correctly.
Question is : Does there exist a graph with 5 vertices which have the following degrees: 2, 4, 4, 4, 4?
So I use Havel Hakimi to solve this question
I start from 4442 then 3331 then 331 then 220 then 1,1,-1
Then once I'm at 1,1,-1 we can say that the graph of the question does not exist since graph with degrees 1,1,-1 does not exist.
Am I right?
Could you help ?
 A: Even without the use of a theorem, with five vertices a vertex of degree four must be adjacent to all other vertices.  In particular, all four of the degree-four vertices must be adjacent to the degree-2 vertex.  This is however a contradiction as the degree-2 vertex could only have been adjacent to two of the degree-four vertices and not all four of them.
A: This simple graph does not exist, which you can also verify with the Erdős–Gallai theorem, however your application of Havel-Hakimi doesn't seem to be completely correct.
We start with $(4,4,4,4,2)$, remove the first entry $d_1=4$ and reduce the next $d_1=4$ entries by $1$ to get $(3,3,3,1)$.
Now we reset the input as $(3,3,3,1)$, remove the first entry $d_1=3$ and reduce the next $d_1=3$ entries by $1$ to get $(2,2,0)$.
Again we reset the input as $(2,2,0)$, remove the first entry $d_1=2$ and reduce the next $d_1=2$ entries by $1$ to get $(1,-1)$.
The sequence $(1,-1)$ obviously isn't graphical so the original sequence $(4,4,4,4,2)$ can't be graphical.
Note that we could have stopped once we reached $(2,2,0)$ since this sequence clearly isn't graphical: there is no graph on 3 vertices such that one vertex has degree $0$ and such that the other two vertices have degree $2$.
A: If $G$ is simple this sequence is not graphical but if $G$ is not simple this sequence is graphical , it's a $C_{5}$ and four vertices of the $C_{5}$ have a loop which counts as $2$ in the degree counting so we have all the degrees of those four vertices is 4 and the degree with the vertex with no loop is 2 which is exactly the sequence $(4,4,4,4,2)$.
