What is maximum number of vertices in a graph that has 35 edges and degree of…
What is maximum number of vertices in a graph that has 35 edges and degree of each vertex is greater than or equal to 3?
Answer: 23 — Key idea: To maximize the number of vertices, make each vertex degree as small as allowed (each degree is at least 3). By the handshaking lemma, the sum of…
Attempted by 109 students.
Show answer & explanation
Correct answer: 23
Key idea: To maximize the number of vertices, make each vertex degree as small as allowed (each degree is at least 3).
By the handshaking lemma, the sum of all degrees equals twice the number of edges, so the sum of degrees is 2E = 2·35 = 70.
If there are n vertices and each has degree at least 3, then the sum of degrees is at least 3n. Therefore 3n ≤ 70, which gives n ≤ 70/3 ≈ 23.33, so n ≤ 23.
We must check whether n = 23 is achievable.
Construct degrees so the sum equals 70 while every vertex has degree ≥ 3: take 22 vertices of degree 3 and 1 vertex of degree 4. The sum is 22·3 + 4 = 66 + 4 = 70.
Check feasibility in a simple graph: the vertex with degree 4 has degree ≤ n − 1 = 22, so this degree sequence does not violate simple-graph degree bounds.
Therefore the maximum possible number of vertices is 23.