Consider the following degree sequence: 5, p, 4, 4, 3, q, 2, 1. The given…
Consider the following degree sequence:
5, p, 4, 4, 3, q, 2, 1. The given sequence is valid for a connected graph and the number of edges is 13, then find the possible values of p and q.
Answer: A. 5,2; C. 4,3; D. 6,1 — Answer: A, C and D are correct options The given degree sequence is: 5,p,4,4,3,q,2,1 The number of edges in the graph is given as 13. Step 1: Use the…
- A.
5,2
- B.
6,4
- C.
4,3
- D.
6,1
Attempted by 102 students.
Show answer & explanation
Correct answer: A, C, D
Answer: A, C and D are correct options
The given degree sequence is: 5,p,4,4,3,q,2,1
The number of edges in the graph is given as 13.
Step 1: Use the Handshaking Lemma
According to the Handshaking Lemma, the sum of degrees of all vertices must be twice the number of edges:
=> ∑degrees=2×(number of edges)
=> 5+p+4+4+3+q+2+1=2×13
=> 19+p+q=26
=> p+q=7
Step 2: Check the Given Answer Choices
We need to find valid (p,q) pairs that satisfy p+q=7 while ensuring the graph remains connected.
Option A: (5,2)
5+2=7 (Valid)
Option B: (6,4)
6+4=10 (Incorrect because it does not satisfy p+q=7p+q=7)
Option C: (4,3)
4+3=7 (Valid)
Option D: (6,1)
6+1=7 (Valid)
Since a connected graph cannot have a vertex with degree 0, Option B is invalid.