1,850 views
1 votes
1 votes
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?

3 Answers

Best answer
6 votes
6 votes

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

selected by
2 votes
2 votes

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

2 votes
2 votes

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

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

Related questions

0 votes
0 votes
3 answers
1
Lucky sunda asked Feb 7, 2017
702 views
According to me option B is correct.
8 votes
8 votes
5 answers
2
smartmeet asked Feb 7, 2017
7,418 views
Suppose datagrams are limited to 1,500 bytes (including header) between source Host A and destination Host B. Assuming a 20-byte IP header and a 20-byte TCP header, how m...