If G is a simple graph with 11 vertices and degree of each vertex is atmost 5,…
If G is a simple graph with 11 vertices and degree of each vertex is atmost 5, then maximum number of edges possible in G is
Answer: B. 27 — By the handshaking lemma, the sum of the degrees of all vertices is equal to twice the number of edges: ∑deg(v) = 2E. Each vertex has degree at most 5, and…
- A.
26
- B.
27
- C.
27.5
- D.
29
Attempted by 191 students.
Show answer & explanation
Correct answer: B
By the handshaking lemma, the sum of the degrees of all vertices is equal to twice the number of edges: ∑deg(v) = 2E.
Each vertex has degree at most 5, and there are 11 vertices, so the sum of degrees is at most 5 × 11 = 55.
Thus, 2E ≤ 55 → E ≤ 27.5.
Since the number of edges must be an integer, the maximum possible value of E is 27.
Loading lesson…