The Gateway to Computer Science Excellence
0 votes

Minimum no of edges necessary in a simple graph with 10 vertices to ensure connectivity is_______.

in Graph Theory by | 251 views
Is answer is 9?
Simple  Connected graph

Maximum  edges possible in complete graph

Minimum edges possible in tree
The ans given in book is 15
i hope the answer provided is wrong,
$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$
@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.

@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



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 .

Can u explain it in a more easy way?

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.

So what should be the answer for this question?
should be 9

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.

1 Answer

+1 vote
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
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,891 answers
118,128 users