Let G be a simple graph with 25 vertices and 6 connected components. Find (i) the minimum number of edges that G can have. (ii) the maximum number of edges that G can have.
What I know:
The maximum degree of a vertex is 24 if the graph is connected.
Best Answer
Let $a_1, \dotsc, a_6$ be the number of vertices of the components. We know that $a_i \geq 1$ and $\sum a_i = 25$.
To find the minimum number of edges of $G$, let's first look at a single connected component. A component with $n$ vertices cannot have less than $n-1$ edges. Also, a star graph is connected and have exactly $n-1$ edges, so we can attain this minimum.
Thus, the minimum number of edges in $G$ will be: $$ \sum_{i=1}^6 (a_i - 1) = \sum_{i=1}^6a_i - 6 = 25 - 6 = 19 $$
The maximum can be found in a similar way. The maximum number of edges in a component with $n$ vertices is $\binom{n}{2}$, that is attained on a complete graph $K_n$. Thus we want to maximize: $$ \sum_{i=1}^6\binom{a_i}{2} = \sum_{i=1}^6 \frac{a_i(a_i-1)}{2} = \frac{1}{2} \left( \sum_{i=1}^6 a_i^2 - \sum_{i=1}^6a_i \right)$$ $$ = \frac{1}{2} \left( \sum_{i=1}^6 a_i^2 - 25 \right)$$
Note that $\sum_{i=1}^6a_i^2$ is convex, so the maximum is attained on the boundary of the region given by $\sum_{i=1}^6a_i = 25$, so we have a maximum when $a_1 = 1$, $a_2 = 1$, $a_3 = 1$, $a_4 = 1$, $a_5 = 1$ and $a_6 = 20$. Hence the maximum number of edges is: $$ \frac{1}{2} \left( 20^2 + 5 - 25 \right) = 190$$ That is attained when the components are five copies of $K_1$ and one $K_{20}$.