Question

Which of the following degree sequences are possible for a simple graph?

a. (5,3,3,3,2,2)
b. (9,8,8,7,4,4,4,2,2,1)
c. (8,6,3,3,2,2,2,1)
d. (6,5,4,4,3,3,3)

Answer 1

Degree sequences (5,3,3,3,2,2), (8,6,3,3,2,2,2,1), and (6,5,4,4,3,3,3) are possible for a simple graph, while degree sequence (9,8,8,7,4,4,4,2,2,1) is not possible.

Step-by-step explanation:

A graph is said to have a degree sequence if the degree of each vertex is listed in non-increasing order. To determine if a degree sequence is possible for a simple graph, we can use the Havel-Hakimi algorithm. This algorithm starts with the highest degree in the sequence and removes that degree and reduces the degrees of the next highest vertices by 1. If at any point the degrees become negative or the sequence cannot be fully processed, then the degree sequence is not possible for a simple graph. Let's apply this algorithm to each of the given degree sequences:

1. (5,3,3,3,2,2): Possible
2. (9,8,8,7,4,4,4,2,2,1): Not possible
3. (8,6,3,3,2,2,2,1): Possible
4. (6,5,4,4,3,3,3): Possible