Is there a simple graph with degree sequence (1,1,3,3,3,4,6,7)? Justify your answer.

Steps to Solve

1. Check the sum of the degree sequence

First, calculate the sum of the given degree sequence. The sum must be even, as each edge contributes two to the sum of degrees.

The sum is: $$ 1 + 1 + 3 + 3 + 3 + 4 + 6 + 7 = 28 $$

Since 28 is even, we can proceed.

2. Apply the Havel-Hakimi algorithm

Next, arrange the degree sequence in non-increasing order: $$ (7, 6, 4, 3, 3, 3, 1, 1) $$

Then, remove the first element (7) and reduce each of the next 7 degrees by 1.

This gives us: $$ (6 - 1, 4 - 1, 3 - 1, 3 - 1, 3 - 1, 1 - 1) = (6, 3, 2, 2, 2, 0) $$

3. Repeat the Havel-Hakimi algorithm

Now we have the new sequence: $$ (6, 3, 2, 2, 2, 0) $$

Arrange in non-increasing order: $$ (6, 3, 2, 2, 2, 0) $$

Remove the first element (6) and reduce the next 6 degrees by 1: $$ (3 - 1, 2 - 1, 2 - 1, 2 - 1, 0) = (2, 2, 1, 0, 0) $$

4. Final iteration of Havel-Hakimi algorithm

Now we have: $$ (2, 2, 1, 0, 0) $$

Arrange in non-increasing order: $$ (2, 2, 1, 0, 0) $$

Remove the first element (2) and reduce the next 2 degrees by 1: $$ (2 - 1, 1 - 1, 0, 0) = (1, 0, 0) $$

5. Check for non-negative values

The final sequence (1, 0, 0) is valid as all degrees are non-negative, indicating it's possible to create a graph with the initial degree sequence.