264 views
0 votes
0 votes
Is there any simple graph with degree sequence

<1,1,1,1,2,2,3,3,3,3>

1 Answer

0 votes
0 votes

Use HAVEL-HAKIMI ALGORITHM

(1) Sort the degree sequence

$$<3,3,3,3,2,2,1,1,1,1>$$

(2) Remove first degree from the above sequence obtained and subtract 1 from that many numbers of degrees ahead of the degree being removed, in this case, subtract from next 3 degrees.

$$<2,2,2,2,2,1,1,1,1>$$

(3) Repeat the previous step again.

$$<1,1,2,2,1,1,1,1>$$

Sort this sequence thereafter, to apply the procedure again.

$$<2,2,1,1,1,1,1,1>$$

(4) Repeat step (2)

$$<1,0,1,1,1,1,1>$$

We can repeat the process again for few more times to obtain a degree sequence consisting of only zeroes. But we can stop right here by saying that the degree sequence obtained is indeed a simple graph as there are even number of 1's in the sequence i.e., even number of vertices with odd degree.

Reference

HTH

Related questions

3 votes
3 votes
0 answers
1
h4kr asked Jan 31, 2023
610 views
Number of possible permutations that can be obtained using stack if the input sequence is 1, 2, 3, 4, 5 (in the order) is