Test series: gatebook mock 2

Question

Consider the collection of all un directed graphs with 10 nodes and 6 edges. Let M and m, respectively, be the maximum and minimum number of connected components in any graph in the collection. If a graph has no self loops and there is at most one edge between any pair of nodes, which of the following is true?

(A) M = 10, m = 10

(B) M = 10, m = 1

(C) M = 7, m = 4

(D) M = 6, m = 4

 

Shouldn't the answer be D?

Answer 1

This is very brilliant question!

We have here, Edges E=6 and Vertices N=10.

A) Maximum Components:

For, Maximum components we should have maximum vertices are disconnected as possible. so for doing that we should have graph, which takes minimum vertices and maximum edges i.e. it is a Complete graph.

So, N(N-1)/2 =E = 6 {No. edges in complete graph} 

::N=4

so, our 4 vertices are utilized to cover 6 edges or we can say we need atleast 4 vertices to cover 6 edges!

So, total components = 1 [complete graph] + 6 [all vertices 'single'] =7

B)Minimum Components

Logic is same but in reverse manner,thus 'we should find graph which take maximum vertices to cover all the edges' i.e. MST

N-1 =E =6 {no.of edges in MST}

::N=7

So,our 7 vertices are utilized to cover 6 edges or we can say we would have at most 7 vertices to cover 6 edges

So, total components = 1 [MST]+ 3 [all vertices 'single'] = 4

Ans is (C) M=7,m=4

Comments

Nice answer

Answer 2

Min connected component will be : e - v = 10-6 = 4
Max connected component :
with 6 vetrices we can have K₄. & all other 6 nodes will be isolated virtices. 
Total connected conent = 1+6 = 7
 

Comments

yup 7 and 4

---

Got it,Thanks :)

Answer 3

For minimum no of connected components , we use the inequality :

n - k  <=  e   <=  (n - k)(n - k + 1) / 2 ,

where n : no of vertices

            e  : no of edges

           k :  no of connected components

Hence to get minimum no of connected components , we use the left inequality as :

         k >=  n - e 

==>   k >=  10 - 6

==>   k >=  4

Hence minimum no of connected components possible i.e.  m  =  4.........(1)

Now for maximum no of connected components , we try to include as many edges as possible in one connected component and the remaining vertex as the isolated (lone) vertex and hence separate connected component..

Here            

        no of vertices  =  10

        no of edges  =  6

Hence we assign these 6 edges to 1 connected component which will be K₄..

Hence we are now left with 6 vertices..

Hence now no of connected components  =  1 + 6  =  7

Hence maximum no of connected components = M = 7

Hence C) is correct answer..