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 _________ .

GATE 2017 · Discrete Mathematics · Degree of Graph · medium

Answer: 16

1. Fix the degree sum: With 25 edges the sum of all degrees equals 50; this is the total degree available to distribute among the vertices.
2. Bound n with the minimum degree: Since every vertex has degree at least 3, the degree sum is at least 3n. Combined with the total 50: 3n <= 50, so n <= 50/3 = 16.67.
3. Take the integer maximum: n must be a whole number, so n <= 16. n = 16 is achievable: give fifteen vertices degree 3 and one vertex degree 5 (sum = 45 + 5 = 50), which a valid simple graph can realise. Hence n_max = 16.