Thread: Graphic Sequence

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 is graphical iff the sequence 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.

What if we have d1 as greater or equal to number vertices in the graph. How long we have to subtract 1 ?