What is the maximum possible number of edges of a graph with n vertices and k components? Following is my attempt:
For maximum possible edges $->$ all k components must be connected sub-graphs
Maximum possible edges in a graph with n vertices = ${n \choose 2}$, I thought of removing k-1 edges, but only to realise that doing so doesn't divide the graph into k components. 
How should I proceed now?
 A: Consider this problem combinatorially.
You have $n$ vertices partitioned into $k$ components. Assume $n \geq k$. 
Consider the equation $n_1+n_2+\cdots+n_k=n$.
For each component with $n_i$ vertices, the maximum number of edges you can generate is $\displaystyle \binom{n_i}{2}$.
So, you want to maximize $\displaystyle \binom{n_1}{2}+\binom{n_2}{2}+\cdots \binom{n_k}{2}$. 
Play with it for a while. The maximum result is obtained when $n_1=n-k+1$, and $n_2=n_3...=n_k=1$, and the maximum number of edges is $\displaystyle \binom{n-k+1}{2}$. 
A: I am assuming your question is the following:

What is the maximum number of edges in a graph with $n$ vertices and $k$ connected components?

This is equivalent to maximizing the function
$$
f(x_1,...,x_k) = \sum_{i} \binom{x_i}{2} =\frac{1}{2} \sum_{i} x_i^2-x_i
$$
subject to the constraints 
$$
\sum_{i}x_i = n
$$
and $x_i \in \mathbb{N}^{>0}$. 
Why? Because of none of the components $C_i$ can have an edge between them and $\binom{|C_i|}{2}$ is the maximum edges subject to this constraint; the $x_i \in \mathbb{N}^{>0}$ is necessary to ensure that there are $k$ components.
From here we have two possible approaches:


*

*combinatorial optimization

*Lagrange multipliers


but the first is much nicer.
Combinatorial approach Notice that if we take a "ball" (i.e. vertex) out of the $x_j$ "box" (i.e. component) and place it in the "$x_i$" box then we get that $\Delta f = x_i-x_j+1$. Therefore it seems that the solution is to just place all of the balls in one box because $x_i>x_j$ implies $f'=f+\Delta f = f+ x_i-x_j+1$ is a better solution. This is not allowed because of the condition $x_i \in \mathbb{N}^{>0}$. But we can set 

$x_1=n-k+1$ and $x_2=...=x_k=1$. 

This is the optimal configuration. Indeed suppose you had any other solution $z_1,...,z_k$ for a contradiction. Order the $z_i$ in decreasing size. Suppose that $z_i >1$ for some $i>2$ then we get that setting $z_i$ equal to $z_i-1$ and $z_1$ equal to $z_1+1$ gives us a better solution contradicting the optimality of the $z_i$. 
