MadeEasy Subject Test: Algorithms - Graph Connectivity

Question

Answer 1

Here the trick is :

To identify that connected component which is maximum sized i.e. maximum no of edges with given no of vertices..Having done that we can accomodate for remaining vertices..

So we know in K₄ , no of edges  =  6

And in the question also no of edges  = 6

Hence using 4 vertices we are able to cover 6 edges and hence it accounts for 1 connected component..

Now we are left with 6 vertices ..So maximum of 6 connected components are possible with these 6 vertices..

Hence total no of connected components = 1 + 6

                                                             = 7

Hence 7 is the correct answer..

Comments

One more way to do :

With $\bf E$ no of edges and $\bf K$ no of connected components: We have the relation:

$\begin{align*} &\bf E \leq \frac{\left ( \bf n-k+1 \right )\left ( \bf n-k \right )}{2} \\ &{\color{blue}{\bf \Rightarrow }} \bf 6 \leq \frac{\left ( \bf 10-k+1 \right )\left ( \bf 10-k \right )}{2} \\ \end{align*}$

• put $k = 12$ from option $B$ ... above condition does not satisfy
• option $C,D$ also elimitated because more than $12$ anyway will not be possible.
• Answer $A$, and above condition also OK with $A$ 

---

Idea here is, to have maximum component, we should accommodate given edges in minimum vertices.
We can accommodate $6$ edges into $4$ vertices, so 6 vertices are left.
total components = $6+1=7$

Answer 2

With this data for numerical type question :

we know the maximum number of edges in k components with n vertices

 E≤ $\frac{(n-k+1)(n-k)}{2}$

6 ≤ $\frac{(10-k+1)(10-k)}{2}$

12 ≤ $(11-k)(10-k)$

Now maximum value of K that satisfy is 7 , you can try with 8,9,10 also.