edited by
873 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.
edited by

2 Answers

3 votes
3 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.
0 votes
0 votes
Consider all the edges in a fully connected subgraph. With 15 edges we can have 6 vertices, and 9 pendant vertices. that is a total of 1+9=10.

 

The task is to exhaust all the edges in one go.

Related questions

0 votes
0 votes
0 answers
1
1 votes
1 votes
1 answer
2