Question

Draw a graph with tow componets that has degree sequence (1,1,1,1,1,3,3,3)

Answer 1

The solution uses the Havel Hakimi Theorem.

The Havel Hakimi Theorem states that:

Suppose that G = (d₁,d₂,d₃,.....,d_n) be a non-increasing sequence.
Consider the new sequence G' = (d₂-1,d₃-1,.......d_d1+1 - 1,d_d1+2,.......d_n) which is obtained from the above sequence by removing the first term d₁ and subtracting 1 from the next d₁ terms.
Then, the new sequence G' is the degree sequence of a graph iff G is the degree sequence of some graph.



Now, turning towards the problem:

For this, we write the degree sequence in non-increasing order :
(3,3,3,1,1,1,1,1)

Step 1: (3,3,3,1,1,1,1,1)
Step 2: (2,2,0,1,1,1,1) = (2,2,1,1,1,1,0)
Step 3: (1,0,1,1,1,0) = (1,1,1,1,0,0)
Step 4: (0,1,1,0,0) = (1,1,0,0,0)

To draw the graph back, we need to follow the steps in reverse and start with (1,1,0,0,0).