\(G\) is an undirected graph with \(n\) vertices and 25 edges such that each…
2017
\(G\) is an undirected graph with \(n\) vertices and 25 edges such that each vertex of \(G\) has degree at least 3. Then the maximum possible value of \(n\) is _________ .
Attempted by 166 students.
Show answer & explanation
Correct answer: 16
Key idea: use the handshaking lemma: the sum of degrees equals twice the number of edges.
Since the graph has 25 edges, the sum of all vertex degrees is 2×25 = 50. Each vertex has degree at least 3, so 3n ≤ 50. Therefore n ≤ 50/3 ≈ 16.66, and the largest integer n satisfying this is 16.
Existence (construction):
Take any 3-regular graph on 16 vertices (a 3-regular graph exists because 16 is even and at least 4). Such a graph has 3×16/2 = 24 edges.
Add one extra edge between two vertices. This increases the edge count to 25 and raises the degrees of those two vertices from 3 to 4, while all other vertices remain degree 3.
Now every vertex has degree at least 3 and the graph has 25 edges, so n = 16 is achievable.
Final answer: 16.
A video solution is available for this question — log in and enroll to watch it.