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 Show 7 previous comments 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.