2 votes 2 votes Graph Theory ace-test-series graph-theory graph-connectivity + – Shivam Chauhan asked Sep 26, 2017 edited Mar 7, 2019 by Rishi yadav Shivam Chauhan 688 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Shivam Chauhan commented Sep 26, 2017 reply Follow Share Please explain above formula for number of edges 0 votes 0 votes Prabhanjan_1 commented Sep 26, 2017 reply Follow Share wkt max no.of edges in a complete graph = nC2 Consider a case where keep n-1 vertices on one side and 1 vertex on other side . Now maximum no of edges in the first one is n-1C2 Still the graph is disconnected. adding edge to vertex 1 makes graph connected. So (n-1) (n-2) / 2 + 1 => 172 0 votes 0 votes Shivam Chauhan commented Sep 26, 2017 reply Follow Share Let G be a graph with n vertices and if every vertex has a degree of at least $\lfloor \frac {n}{2} \rfloor$ then G is connected. Degree of each vertex = 20/2 = 10. Total degree = 10*20 = 200. Number of edges = 200/2 =100 Where am I wrong? Please explain 0 votes 0 votes Prabhanjan_1 commented Sep 26, 2017 reply Follow Share Consider two cases here 1) To make it simple , we take a 5 vertex graph, Consider your approach .... Now each vertex must be having atleast a degree of 2. So total number of edges i get are = 6edges. 2) Consider the above approach Now one side is fully connected => gives 6 edges adding one edge makes it to connect entire graph = > 7 edges. BUT ,Consider (1) ,, i can show a graph with 6 edges and is not connected .(connecting everything on one side) but one cannot show a graph with 7 edges and not connected. 0 votes 0 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes Here they are asking Necessary condition which will ensure graph will connected in any case Also e should be strictly greater than (n-1)(n-2)/2 aehkn answered Sep 27, 2017 selected Sep 27, 2017 by Shivam Chauhan aehkn comment Share Follow See 1 comment See all 1 1 comment reply Shivam Chauhan commented Sep 27, 2017 reply Follow Share Thanks aehkn and Prabhanjan_1 for the help. 0 votes 0 votes Please log in or register to add a comment.