# Graphic Sequence

• Sep 15th 2010, 08:08 PM
jzellt
Graphic Sequence
How do I show whether or not this a graphic sequence:

5,5,4,3,2,2,2,1

Thanks...
• Sep 15th 2010, 08:16 PM
Traveller
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.
• Sep 15th 2010, 09:39 PM
jzellt
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?
• Sep 15th 2010, 10:56 PM
Traveller
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.
• Sep 19th 2010, 05:20 AM
kumaran5555
What if we have d1 as greater or equal to number vertices in the graph. How long we have to subtract 1 ?