832 views
0 votes
0 votes
Let G be a undirected graph with 35 edges and degree of each vertex is at least 3 then maximum number of vertices possible in G is

(A) 22
(B) 23
(C) 24
(D) 25

P.S. Explain with ease, if possible!

1 Answer

Best answer
7 votes
7 votes
Let $m$ be mindegree and $M$ be maxdegree of a graph, then $\color{navy}{m \le \frac{2E}{V} \le M}$

$m = 3, E = 35, V = ...?$

So, $3 \le \frac{2*35}{V}$

$V\le \frac{2*35}{3}$

$V \le 23.333 \color{maroon}{\Rightarrow V = 23}$
selected by

Related questions

0 votes
0 votes
1 answer
1
mb14 asked May 28, 2018
393 views
In this graph it is said that $a,e,b,c,b$ is a path. But according to definition- in a path vertices and edges can't repeat so why this is a path. confused please clarify...
0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4
Pavan Kumar Munnam asked May 12, 2017
374 views
algorithm to find more than one path between any two vertices of a graph G=(V,E) , with a complexity of O(VE) ?