ACE Bits and bYtes

Question

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

Comments

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.

Answer 1

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