GO Classes 2024 | IIITH Mock Test 5 | Question: 50

Answer 1

Havel-Hakimi Theorem: The non-increasing sequence $(d_{1},d_{2},\ldots,d_{n})$ is graphic if and only if the sequence $(d_{2}-1,d_{3}-1,\ldots, d_{n} – 1)$ is also graphic.

The Havel–Hakimi theorem says that we can test if a sequence is graphical by the following procedure:

1. Sort the sequence in decreasing order.
2. If the first term is $k$,
   1. remove the first term,
   2. subtract $1$ from the $k$ following terms. 
3. If a negative number is obtained, stop. Otherwise, repeat from step $1$.

$\textbf{Note:}$ A sequence with all zeroes is graphic since we can always draw that many isolated vertices.

$\implies$ For any graph the sum of the degrees of the vertices equals twice the number of edges.It means sum of the degrees of the vertices is even.

$\implies$ Sum of the all odd degree vertices is even.

• Take option $(A):5+5+5+3+3=21(odd)\implies$ Not possible.
• Take option $(B):7+7+5+5+3+3+3+3+1=37(odd)\implies$ Not possible.
• Take option $(C):1+1+1+3+3+5+5=19(odd)\implies$ Not possible.
• Take option $(D):7+7+5+5+3+3+1+1=32(even)\implies$ may be possible.

Now applying the Havel-Hakimi Theorem on option (D).

From $(7,7,6,6,5,5,4,4,3,3,2,2,1,1)$ we:

• Remove $7$ and then subtract $1$ from the next seven terms to get $(6,5,5,4,4,3,3,3,3,2,2,1,1)$
• Remove $6$ and then subtract $1$ from the next six terms to get $(4,4,3,3,2,2,3,3,2,2,1,1)$ and sort to get $(4,4,3,3,3,3,2,2,2,2,1,1)$
• Remove $4$ and then subtract $1$ from the next four terms to get $(3,2,2,2,3,2,2,2,2,1,1)$ and sort to get $(3,3,2,2,2,2,2,2,2,1,1)$
• Remove $3$ and then subtract $1$ from the next three terms to get $(2,1,1,2,2,2,2,2,1,1)$ and sort to get $(2,2,2,2,2,2,1,1)$
• Remove $2$ and then subtract $1$ from the next two terms to get $(1,1,2,2,2,1,1)$ and sort to get $(2,2,2,1,1,1,1)$
• Remove $2$ and then subtract $1$ from the next two terms to get $(1,1,1,1,1,1)$
• Remove $1$ and then subtract $1$ from the next one terms to get $(0,1,1,1,1)$ and sort to get $(1,1,1,1,0)$
• Remove $1$ and then subtract $1$ from the next one terms to get $(0,1,1,0)$ and sort to get $(1,1,0,0)$

We can draw the graph for the above-degree sequence.

Therefore, the given degree sequence is graphic.

So, the correct answer is (D).