Maximum number of vertices possible in a simple graph if 35 edges and degree…
Maximum number of vertices possible in a simple graph if 35 edges and degree of each vertex is at least 3 is _____?
Answer: 23 — Step 1: In any simple graph, the sum of degrees of all vertices is equal to twice the number of edges. Given 35 edges, total degree sum = 2 × 35 = 70. Step 2:…
Attempted by 25 students.
Show answer & explanation
Correct answer: 23
Step 1: In any simple graph, the sum of degrees of all vertices is equal to twice the number of edges. Given 35 edges, total degree sum = 2 × 35 = 70.
Step 2: Each vertex has degree at least 3. So, if there are n vertices, total degree ≥ 3n.
Step 3: Since total degree = 70, we have 3n ≤ 70 → n ≤ 70/3 ≈ 23.33.
Step 4: Since n must be an integer, maximum possible value is 23. Therefore, the maximum number of vertices is 23.
A video solution is available for this question — log in and enroll to watch it.