How do I show whether or not this a graphic sequence:

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

Thanks...

Printable View

- Sep 15th 2010, 08:08 PMjzelltGraphic 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 PMTraveller
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 PMjzellt
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 PMTraveller
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 AMkumaran5555
What if we have d1 as greater or equal to number vertices in the graph. How long we have to subtract 1 ?