recategorized by
2,790 views
1 votes
1 votes

A simple undirected graph ‘X’ has 10 vertices. If ‘X’ has 5 equally sized connected components, the maximum number of edges in graph ‘X’ is _________.

recategorized by

2 Answers

Best answer
9 votes
9 votes
Yes Answer is 5.
But in general form we can conclude it like --

We have 'n' vertices and 'k' equally sized connected components.  
Then each components has (n/k) vertices . And now we will check maximum edges in a particular components using formula of complete graph(nC2) . So here,  maximum edges in 1 component  =  [n/k] [(n/k)-1] / 2  = x(say it)

And total edges will be -- = number of components* maximum edges in each component=  k * x.

You can simplify more and you will get, maximum number of edges =  [n *(n-k)] /2k.

Now put n=10, k=5
maximum edges= 10*5/2*5  = 5
selected by
0 votes
0 votes
ans is 5.

bz component of equal size then no of vertices in each componet =n/k=10/5=2

no of egdes=k*(n/k-1)

Related questions

3 votes
3 votes
3 answers
3
sharma.abhilasha asked Dec 15, 2015
2,908 views
In a simple connected undirected graph with n nodes(where n≧2), The maximum number of nodes with distinct degrees is n-1n-2n-32
2 votes
2 votes
0 answers
4
Parshu gate asked Nov 11, 2017
1,141 views
Let G be a planar Graph Such that every phase is bordered by exactly 3 edges which of the following can never be value for X(G) a)2 b)3 C)4 d)none of these