44 votes 44 votes $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 _________ . Graph Theory gatecse-2017-set2 graph-theory numerical-answers degree-of-graph + – Madhav asked Feb 14, 2017 retagged Jun 23, 2017 by Arjun Madhav 17.3k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 75 votes 75 votes Let $m$ be minimum degree and $M$ be maximum degree of a graph, then $\color{navy}{m \le \frac{2E}{V} \le M}$ $m = 3, E = 25, V = ...?$ So, $3 \le \frac{2*25}{V}$ $V\le \frac{50}{3}$ $V \le 16.667 \color{maroon}{\Rightarrow V = 16}$ mcjoshi answered Feb 14, 2017 edited Jan 1, 2018 by Puja Mishra mcjoshi comment Share Follow See all 10 Comments See all 10 10 Comments reply Tuhin Dutta commented Jan 2, 2018 reply Follow Share Thanks 0 votes 0 votes neel19 commented Apr 12, 2021 reply Follow Share If max degree were given in the question instead of min, then we have to apply ceil? 0 votes 0 votes rajankakaniya commented Jun 20, 2021 reply Follow Share Yes in that case we can apply ceil. But, minimum vertices n will be 17 (not maximum). @neel19 0 votes 0 votes ankit3009 commented Sep 29, 2021 reply Follow Share @rajankakaniya please elaborate. I didn’t understood your point. 0 votes 0 votes Kiyoshi commented Dec 8, 2021 reply Follow Share @rajankakaniya Yes in that case we can apply ceil. But, minimum vertices n will be 17 (not maximum). How can you explain?? 0 votes 0 votes ankit3009 commented Dec 8, 2021 reply Follow Share @ASNR1010 how can we tag people using @ ? Sorry for this silly question but I tried, not working for me. 1 votes 1 votes Kiyoshi commented Dec 8, 2021 reply Follow Share Right click on the user and copy link… Like yours… https://gateoverflow.in/user/ankit3009 Now remove the front and add ‘@’ or not @ankit3009 Now it’s done.🙂 1 votes 1 votes ankit3009 commented Dec 8, 2021 reply Follow Share Thank you @ASNR1010! :) 2 votes 2 votes rajankakaniya commented Dec 8, 2021 reply Follow Share G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at most 3. Then the minimum possible value of n is ? If question like this then below is answer. Let, Max degree M=3 2e/n <= M 2(25)/n <= 3 50/3 <= n 16.6666 <= n Here n can not be 16 or less. So, n>=17. So, minimum n possible is 17. 1 votes 1 votes tusharb commented Jan 11, 2022 reply Follow Share @rajankakaniya I didn’t get the concept of ceil and floor here, Can you please explain it a bit more? 0 votes 0 votes Please log in or register to add a comment.
11 votes 11 votes k.V<=2E so,3V<=2*25=$\left \lfloor 50/3 \right \rfloor =16$ Ans:16 Arnabi answered Feb 14, 2017 Arnabi comment Share Follow See all 0 reply Please log in or register to add a comment.
8 votes 8 votes According to Handshaking Lemma: The Sum of degree of all the vertices is equal to the twice the number of edges. in our question: Number of vertices = n Number of edges = 25 3 * n = 2 * 25 3n=50 n=16.667 n =16 which is the maximum possible value akash.dinkar12 answered Apr 13, 2017 reshown May 26, 2018 by akash.dinkar12 akash.dinkar12 comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes 2*e>=n*k 2*25>=n*3 n<=16.666 so ,n=16 aditya930 answered Apr 16, 2017 aditya930 comment Share Follow See all 0 reply Please log in or register to add a comment.