Project ForgeDiscrete Mathematics
Graph Theory
GATE 2017
Medium
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 ____.
16
Explanation
By the Handshaking Lemma, the sum of all vertex degrees = 2×25 = 50. If every one of the n vertices has degree at least 3, the sum of degrees is at least 3n, so 3n ≤ 50, giving n ≤ 16.67 — since n must be an integer, the maximum possible value is 16.
Source: GATE CS 2017 (Session 2) (2017)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.