Answer to Question #222054 in Discrete Mathematics for Sach

Question

Hence show that the maximum number of edges in a disconnected graph of n vertices and k components
is (n-k)(n-k+1)/2.

Answer 1

Let $n_1, n_2,\dots,n_k$ denote the number of vertices in each of $k$ components of the graph.

Then the $i$-th component contains not more than $n_i(n_i-1)/2$ edges. We can add more edges to make a complete subgraph from each of the components. Then each of the components will contain exactly $n_i(n_i-1)/2$ edges.

If $n_i\geq n_j>0$, then we can take a vertex from the j-th component, deleting $n_j-1$ edges, and add this vertex to the i-th component, connecting it with other vertices by $n_i>n_j-1$ edges.

By acting in this way, we can accumulate the maximum number of vertices, $n-k+1$, in one component with all possible edges, whereas all other components consist of one vertex without any edges. Then we obtain a graph with k components, having the maximum possible number of edges. This number equals to $(n-k)(n-k+1)/2$.

Therefore, for the general simple graph with $n$ vertices and $k$ components, the total number of edges does not exceed $(n-k)(n-k+1)/2$.