The Gateway to Computer Science Excellence

0 votes

+1

$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$

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$

0

@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

@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

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** .

+1

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.

0

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.

52,218 questions

59,891 answers

201,086 comments

118,128 users