Does the degree sequence 6, 5, 5, 5, 4, 4, 2, 1 violate the Havel-Hakimi…
Does the degree sequence 6, 5, 5, 5, 4, 4, 2, 1 violate the Havel-Hakimi criterion?
Answer: C. False — No. Apply the Havel-Hakimi reductions: (6, 5, 5, 5, 4, 4, 2, 1) → (4, 4, 4, 3, 3, 1, 1) → (3, 3, 3, 2, 2, 1) → (2, 2, 2, 1, 1) → (1, 1, 1, 1) → (1, 1, 0) →…
- A.
True
- B.
True, but only after sorting
- C.
False
- D.
None of the above
Attempted by 253 students.
Show answer & explanation
Correct answer: C
No. Apply the Havel-Hakimi reductions:
(6, 5, 5, 5, 4, 4, 2, 1)
→ (4, 4, 4, 3, 3, 1, 1)
→ (3, 3, 3, 2, 2, 1)
→ (2, 2, 2, 1, 1)
→ (1, 1, 1, 1)
→ (1, 1, 0)
→ (0, 0)
The process ends with all zeros, so the sequence is graphical. Therefore, it does not violate the Havel-Hakimi criterion, and the correct answer is False.
Loading lesson…