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! Graph Theory graph-theory engineering-mathematics discrete-mathematics + – smartmeet asked Jan 18, 2017 smartmeet 863 views answer comment Share Follow See 1 comment See all 1 1 comment reply Turning Turing commented Jan 24, 2017 reply Follow Share Bro don't mug formulas in graph theory only remember handshaking for such problems thats enough 0 votes 0 votes Please log in or register to add a comment.
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}$ mcjoshi answered Jan 18, 2017 • selected Jan 20, 2017 by Sushant Gokhale mcjoshi comment Share Follow See all 3 Comments See all 3 3 Comments reply smartmeet commented Jan 18, 2017 reply Follow Share so is this some fix formula? 0 votes 0 votes mcjoshi commented Jan 18, 2017 reply Follow Share Yes, handy sometimes. 1 votes 1 votes Dhananjay2017 commented Jan 27, 2017 reply Follow Share We can easily derive or find out . Not require to remember We know that , V * degree = 2e V * minDegree<= 2e //// degrees of vertices may be d , d+ 1 , d+ 3 minDegree <= 2e /V 1 votes 1 votes Please log in or register to add a comment.