34 votes 34 votes What is the number of vertices in an undirected connected graph with $27$ edges, $6$ vertices of degree $2, 3$ vertices of degree $4$ and remaining of degree $3$? $10$ $11$ $18$ $19$ Graph Theory gateit-2004 graph-theory graph-connectivity normal + – Ishrat Jahan asked Nov 2, 2014 • edited May 27, 2018 by kenzou Ishrat Jahan 13.0k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply set2018 commented Nov 13, 2017 reply Follow Share number of vertices 9 votes 9 votes Anishag26 commented Dec 10, 2021 reply Follow Share let x be the no. of vertices to be calculated. According to the Handshaking lemma , The sum of degree of all the vertices = 2* |E| 6 * 2 + 3 * 4 + (x-9) * 3 = 2 * 27 → 12 + 12 + 3x – 27 = 54 → 24 + 3x = 54 + 27 → 3x = 54 + 27 – 24 → 3x = 57 → x = 19 So , the no. of vertices is (D) 19 0 votes 0 votes Please log in or register to add a comment.
Best answer 39 votes 39 votes sum of degree of all the vertices $= 2 *$ number of edges. $2\times 6 + 4\times 3 + 3\times x = 27\times 2$ $x=10.$ Number of vertices $= 6 + 3 +x = 19.$ The correct answer is (D). suraj answered Nov 21, 2014 • edited May 27, 2018 by kenzou suraj comment Share Follow See all 2 Comments See all 2 2 Comments reply rajsh3kar commented Jan 5, 2015 reply Follow Share so given total edges 27 6 vertices having degree 2 means 12 edges 3 vertices having degree 4 means 12 edges so total 24 edges 27- 24 gives 3 edges remaining there is possibility of only one vertex ans is 6+3+1=10 ? i think this is also possible correct this if it is wrong 0 votes 0 votes Anurag_s commented Jan 5, 2015 reply Follow Share Whenever you add an edge in graph it increases the total digree by 2.thats why sum of digrees=2*no. Of edges. Edge is connecting two vertices at a time 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes Let x = Total no. of vertices By Handshaking Lemma, 6 * 2 + 3 * 4 + (x - 9) * 3 = 27 * 2 24 + (x - 9) * 3 = 54 x = 19 keshore muralidharan answered Aug 29, 2020 keshore muralidharan comment Share Follow See all 0 reply Please log in or register to add a comment.