Which of the following degree sequence diagrams are invalid for a connected…
Which of the following degree sequence diagrams are invalid for a connected graph with 6 vertices?
Answer: A. 5,5,3,2,2,1; B. 6,5,4,3,2,1; D. 5,4,3,2,2,1 — To determine if a degree sequence is valid for a connected graph with 6 vertices, apply the following checks: 1. The sum of all degrees must be even…
- A.
5,5,3,2,2,1
- B.
6,5,4,3,2,1
- C.
2,2,2,2,1,1
- D.
5,4,3,2,2,1
Attempted by 138 students.
Show answer & explanation
Correct answer: A, B, D
To determine if a degree sequence is valid for a connected graph with 6 vertices, apply the following checks:
1. The sum of all degrees must be even (handshaking lemma).
2. The maximum degree must be less than the number of vertices (n = 6).
3. Use the Havel-Hakimi algorithm to verify if the sequence is graphical.
4. For connected graphs, ensure the sequence can form a connected structure (e.g., no isolated components).
Apply these checks to each option.