0 votes 0 votes Minimum no of edges necessary in a simple graph with 10 vertices to ensure connectivity is_______. Graph Theory graph-theory graph-connectivity + – abhishek1995_cse asked Jul 23, 2018 abhishek1995_cse 1.3k views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply Show 10 previous comments rajatmyname commented Aug 13, 2018 reply Follow Share So what should be the answer for this question? 0 votes 0 votes Shaik Masthan commented Aug 13, 2018 reply Follow Share should be 9 0 votes 0 votes Debanjan Dey commented Dec 4, 2018 reply Follow Share Is it 9? I have doubt. As mentioned, no. of edges = 9 is the necessary condition for the graph to be connected. Means, even if the graph has 9 edges then the graph may not be connected (some vertices may have more than one paths while other vertices are left out). But the question is asking to ensure that the graph is connected, probably this means by adding these many edges, the graph must be connected. So we must check that addition of new edges doesn't add degree to already connected vertices. This can be ensured only if the rest of the vertices are completely connected. 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes 37 if the graph contain 36 we can construct a simple connected graph with 9 vertices so one vertex become isolated it become disconnected graph gparamesh.1997 answered Aug 8, 2018 gparamesh.1997 comment Share Follow See all 0 reply Please log in or register to add a comment.