Question

If G is a simple graph with 15 vertices and degree of each vertex is at most 7, then maximum number of edges possible in G is ______.

• A. 55
• B. 52
• C. 53
• D. 54

Answer 1

The correct option is B 52

option (a)

By Sum of degrees theorem, if degree of each vertex is at most k then

$K|V|\ge 2|E|$

$7\times \left(15\right)\ge 2|E|$

$\Rightarrow |E|\le 52.5$

$\Rightarrow |E|\le 52$

$\therefore$ The Maximum edges possible = 52