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

Answer 1

Data:

d_min = 3

edges = |E| = 25

Formula:

\({{\rm{d}}_{{\rm{min}}}}{\rm{\;}} \le \frac{{2\left| {\rm{E}} \right|}}{{\left| {\rm{n}} \right|}} \le {\rm{\;}}{{\rm{d}}_{{\rm{max}}}}\)

Calculation

\(3{\rm{\;}} \le \frac{{2 \times 25}}{{\rm{n}}}\)

\({\rm{n\;}} \le \frac{{2 \times 25}}{3} \le 16.66\)

∴ n_max = 16

So, maximum possible value of n is 16.