GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 10

Question

The maximum number of edges a graph with $45$ vertices, and $15$ connected components is ________

Answer 1

The maximum number of edges is clearly achieved when all the components are complete.

Moreover the maximum number of edges is achieved when all of the components except one have one vertex. The proof is by contradiction. Suppose the maximum is achieved in another case. Then there exist two components with more than one vertex -- say the number of vertices are $n$ and $m$ and $n,m > 1$. Pick the one with the less vertices, say - $m$ vertices. Take one of it vertex and delete it removing $m-1$ edges. Now add a new vertex to the component with $n$ vertices and join it to all its vertices, adding $n$ edges. This graph has more edges (as we assumed $n>m$), contradicting the maximality of the graph.

Hence, the maximum number of edges is achieved when only one of the components has more than one vertex. In this case the biggest component will have $n-k+1$ vertices and is the only one with edges.

So, it will have $\dfrac{(n-k+1)(n-k)}{2}$ edges.

Maximum number of edges with $n=45$ vertices and $k=15$ connected components $=\dfrac{(45-15+1)(45-15)}{2}=465$.

So, the correct answer is $465$.

Answer 2

Let suppose the For the complete graph 

Each vertex will (n-1) vertex is connected to it. 

Now think

 

Vertices	45	44	...
Removing Edges (it will removed from the total edges)	44	43	..
Resulting Component	2nd	3rd	..										15th

Here the we need the 15th component . 

We know that that total 45 Vertices of edges is equal to n(n-1)/2 which is equal to the 990 edges

Now After each addition of component , we have to remove the edges . 

we will us Sum of the AP 
a1 =44 and d=-1

note that on removing the 44 edges this will resulting into  two component 

so for the sequence we need to go only for 14 sequence not for the 15 ,On the 14th sequence we will get the 15th component 

a14= 44+(13)(-1)

a14= 31

So , S14 = 14/2( 2(44) + 13(-1))
       S14= 525

Answer-> 990 – 525 = 465