How do I show whether or not this a graphic sequence:
5,5,4,3,2,2,2,1
Thanks...
From Wolfram Mathworld :
Havel (1955) and Hakimi (1962) proved another characterization of graphic sequences, namely that a degree sequence with n>=3 and $\displaystyle d_1>=1$ is graphical iff the sequence $\displaystyle {d_2-1,d_3-1,...,d_(d_1+1)-1,d_(d_1+2),...,d_p}$ is graphical.
Graphic Sequence -- from Wolfram MathWorld
The sequence in the successive steps would look like:
5 5 4 3 2 2 2 1
4 3 2 1 1 2 1
4 3 2 2 1 1 1
2 1 1 0 1 1
2 1 1 1 1 0
0 0 1 1 0
The last sequence is clearly graphic. So the first one will be graphic too.
I still have a question about how you went from the original to the second line:
5 5 4 3 2 2 2 1
4 3 2 1 1 2 1
So you deleted the front 5 and subtracted 1 from 5,4,3,2,2. Why are the last two of the second sequence still 2,1? Shouldn't we subtract 1 from those also?
No, what we are doing is equivalent to removing a vertex and and deleting its incident edges. A vertex is adjacent exactly to the number of vertices as its degree. So a vertex with degree 5 would be adjacent to exactly 5 vertices. Now, if you remove the edges between this vertex and its neighbours, each of the 5 neighbours would lose 1 from their degrees.