in DS edited by
350 views
0 votes
0 votes
There are 15 vertices and 15 edges in some graph. Now, these edges are arranged in such a way that maximum number of connected components are created in the graph. Find the connected components created.

(A) 8  (B) 9  (C) 10  (D) 11

Please explain your answer.
in DS edited by
350 views

2 Answers

2 votes
2 votes
We need maximum no of component so we have to find a connected component which cover all the edges with as minimum vertices possible. Now this can be possible if the connected component is a complete graph which contains maximum number of edges and the remaining vertices will create distinct connected component with no edges.

So, Now say the component which cover the edges say have n vertices,

So number of edges =$\frac{n*(n-1)}{2}$

$\frac{n*(n-1)}{2}= 15$

$n = 6$

So, We have a component of 6 vertices which cover all the edges and rest 9 vertices have no edges creating 9 isolated connected component.

so we have total 10 maximum number of connected components possible.

4 Comments

@Arjun sir in this case no of component will decrease to 9 .

Here two possibilities are possible:-

1)  we can use one component consist of 7 vertices which can have 16 edges. rest 8 vertices contribute to 8 connected component . So we end up with 9 component .

2)   We can use one component of 6 vertices which will give 15 edges. We left with 1 more edges for which we need 2 vertices. So for 16 edges we end up with two component one of with 6 vertices and another with 2 vertices . Rest 7 vertices contribute 7 connected component . So here also we end up with 2+7=9 component at max .

0
0
edited by

@Kabir5454

Thanks for your answer. I completely understand the solution. But what I am worrying about is can’t the graph have self loops or parallel edges?

If we consider only self loop then we can put 15 edges in one vertex only, as self loop. Hence it will result 15 connected components in total.

If we consider parallel edges and self loops then we can put all 15 edges in 2 vertices hence it will result total 14 connected components.

Please let me know where I am going wrong if it is a wrong approach.

0
0
Bro I have consider  the graph to be a simple graph . In the question it is not mentioned so i consider it to be simple graph . If we using parallel edge and self loop then the problem will not be interested i guess. As nothing is mentioned your approach is correct. But in exam it should be mentioned.
1
1
0 votes
0 votes
Minimum number of connected in graph containing n vertices and k edged are n-k.  Now the question about max right let I be smalles interger such that i(i-1)/2 >= k then max connected components is n-i+1

Here such I is 6 sk 15-6+1= 10

Related questions