Example 1:
S = 4, 3, 3, 3, 1
Where n = 5 (no. of vertices)
Step 1. Degree of all vertices is less than or equal to n ( no.of vertices)
Step 2. Odd number vertices are four.
Step 3. There is no degree less than zero.
Step 4. Remove ‘4’ from the sequence and subtract 1 from the remaining new sequence and arrange again in non-increasing order to get
S = 2,2,2,0
Step 5. Again remove ‘2 ‘ from the sequence and subtracting 1 from the remaining new sequence and arrange in non-increasing order we get
S= 1,1,0
Repeating the above step
S= 0,0
Step 6. Since all the deg remaining in the sequence is zero, the given sequence is graphical.
Example 2:
Consider the degree sequence: S = 7, 5, 5, 4, 4, 4, 4, 3
Where n = 8 (no. of vertices)
Step 1. Degree of all vertices is less than or equal to n ( no.of vertices)
Step 2. Odd number vertices are four.
Step 3. There is no degree less than zero.
Step 4. Remove ‘7’ from the sequence and subtract 1 from the remaining new sequence and arrange again in non-increasing order to get
S = 4, 4, 3, 3, 3, 3, 2
Step 5. Now remove the first ‘4 ‘ from the sequence and subtract 1 from the remaining new sequence to get:
S = 3, 2, 2, 2, 3, 2
rearrange in non-increasing order to get:
S = 3, 3, 2, 2, 2, 2
Repeating the above step we get following degree sequences:
S = 2, 2, 2, 1, 1
S = 1, 1, 1, 1
S = 1, 1, 0
S = 0, 0
Step 6. Since all the deg remaining in the sequence is zero, the given sequence is graphical (or in other words, it is possible to construct a simple graph from the given degree sequence).
If during the recursive process I end up with a sequence of vertices that does not make a graph (checked by handshaking lemma) is the sequence non-graphical (i.e. fails the test)?
#graph theory:Which of the following lists are the degrees of all the vertices of a graph:
(i) 1, 2, 3, 4, 5 (ii) 3, 4, 5, 6, 7
(iii) 1, 4, 5, 8, 6 (iv) 3, 4, 5, 6
then
(A) (i) and (ii)
(B) (iii) and (iv)
(C) (iii) and (ii)
(D) (ii) and (iv)
Hi Divya,
The answer is actually None of these. Not sure why that’s not an option here.
Reason for all is same, as all 4 given sequences have at least one degree (d) value greater than or equal to total number of nodes (total number of terms in the degree sequence)
-Thanks
Team Coddicted