Question

Give an example of the following or explain why no such example exists.

(a) a graph with degree sequence s: (3, 3, 2, 2, 1, 1, 1)
(b) a graph with degree sequence s: (4, 4, 3, 3, 2, 1, 1)

Answer 1

There is no graph with the degree sequence (3, 3, 2, 2, 1, 1, 1). An example of a graph with the degree sequence (4, 4, 3, 3, 2, 1, 1) is a graph with two disconnected squares.

Step-by-step explanation:

(a) The degree sequence (3, 3, 2, 2, 1, 1, 1) implies that there are 3 vertices with degree 3, 2 vertices with degree 2, and 3 vertices with degree 1. To determine if a graph exists with this degree sequence, we need to check if the sum of the degrees is even. In this case, 3+3+2+2+1+1+1=13, which is odd. Therefore, no such graph exists with this degree sequence.

(b) The degree sequence (4, 4, 3, 3, 2, 1, 1) implies that there are 2 vertices with degree 4, 2 vertices with degree 3, 1 vertex with degree 2, and 2 vertices with degree 1. The sum of the degrees is 4+4+3+3+2+1+1=18, which is even. This means that a graph with this degree sequence can exist. An example of such a graph is a graph with two disconnected squares, each having one vertex of degree 4 and three vertices of degree 1.