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.2k views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply Siddharth Bhardawaj commented Jul 24, 2018 reply Follow Share Is answer is 9? 0 votes 0 votes Shaik Masthan commented Jul 24, 2018 reply Follow Share Simple Connected graph Maximum edges possible in complete graph Minimum edges possible in tree 0 votes 0 votes abhishek1995_cse commented Jul 25, 2018 reply Follow Share The ans given in book is 15 0 votes 0 votes Shaik Masthan commented Jul 25, 2018 reply Follow Share i hope the answer provided is wrong, 0 votes 0 votes sourav. commented Jul 25, 2018 reply Follow Share $9$ is wrong ..with $9$ edges it may be disconnected. take $4$ edges and make it a complete graph..$6$ edges will be wasted there and you have $3$ edges left but you have remaining $6$ vertices too so it will be disconnected it should be $\binom{n-1}{2}+1=\frac{9 \times 8}{2}+1=37$ 2 votes 2 votes Abhisek Das commented Jul 25, 2018 reply Follow Share @Sourav The explanation of your example is flawed. When you are considering 4 vertices,you need minimum 3 edges not 6 to make it connected. 0 votes 0 votes sourav. commented Jul 25, 2018 reply Follow Share @abhishek you mean for $4$ vertices ,minimum $3$ vertices are required to make it connected? but $3$ vertices are not sufficient.Don't say that i am taking maximum 0 votes 0 votes sourav. commented Jul 25, 2018 reply Follow Share if you co-relating this with the property of tree then you are wrong! A graph of $n$ nodes is a tree if it have $n-1$ edges and it is connected . 0 votes 0 votes abhishek1995_cse commented Jul 25, 2018 reply Follow Share Can u explain it in a more easy way? 0 votes 0 votes Shaik Masthan commented Jul 26, 2018 reply Follow Share if you have n vertices, think n-1 vertices are forming complete graph, therefore $\binom{n-1}{2}$ edges are used. therefore with one more edge you should connect the remaining vertex. total edges = $\binom{n-1}{2}$ + 1 but this is not necessary condition, it is sufficient condition. 1 votes 1 votes 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.