Question

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

• A. 16

Answer 1

The correct option is A 16
Number of vertices:
$n\le ?$

Number of vertices:
|E| = 25

Now since each vertex has at least 3 degree
and 2|E| = $\sum$degree
i.e., $2|e|\ge 3n$
$n\le 2|E|/3$

$\Rightarrow n\le \frac{2\times 25}{3}\le 16.66$

So n is at most 16.