Question

Determine if the following sequences are graphical. If so, draw a graph with the given degree sequence. If not, explain why not. (a) ( 6,5,5,4,3,2,1,1) (b) ( 5,5,4,4,3,2,1,1,1 )

Answer 1

To determine if a sequence is graphical, use the Havel-Hakimi algorithm. (a) The sequence (6,5,5,4,3,2,1,1) is not graphical. (b) The sequence (5,5,4,4,3,2,1,1,1) is graphical.

Step-by-step explanation:

A graphical sequence is a sequence of integers that can be represented by a graph with the given degree sequence. To determine if a sequence is graphical, we can use the Havel-Hakimi algorithm:

1. Arrange the sequence in descending order.
2. If the sequence contains a negative integer or a 0, it is not graphical.
3. If all the integers are 1, it is graphical.
4. Remove the first integer, say 'n', and subtract 1 from the next 'n' integers in the sequence.
5. Repeat steps 2-4 until the sequence is empty or contains a negative integer.
6. If the sequence becomes empty, it is graphical; otherwise, it is not graphical.

(a) (6,5,5,4,3,2,1,1):

1. Arrange the sequence in descending order: (6,5,5,4,3,2,1,1).
2. Remove the first integer '6' and subtract 1 from the next 6 integers: (4,4,4,3,2,1,1).
3. Remove the first integer '4' and subtract 1 from the next 4 integers: (3,3,2,1,1).
4. Remove the first integer '3' and subtract 1 from the next 3 integers: (2,2,1,0).
5. The sequence contains '0', which means it is not graphical. Therefore, the sequence (6,5,5,4,3,2,1,1) is not graphical.

(b) (5,5,4,4,3,2,1,1,1):

1. Arrange the sequence in descending order: (5,5,4,4,3,2,1,1,1).
2. Remove the first integer '5' and subtract 1 from the next 5 integers: (4,4,3,3,2,1,1,1).
3. Remove the first integer '4' and subtract 1 from the next 4 integers: (3,3,2,2,1,1,1).
4. Remove the first integer '3' and subtract 1 from the next 3 integers: (2,2,1,1,1,1).
5. Remove the first integer '2' and subtract 1 from the next 2 integers: (1,1,0,0,1,1).
6. Remove the first integer '1' and subtract 1 from the next 1 integer: (0,0,0,0,1,1).
7. Remove the first integer '0' and calculate the next 0 integers: (0,0,0,0,0,0).
8. The sequence becomes empty, which means it is graphical. Therefore, the sequence (5,5,4,4,3,2,1,1,1) is graphical.