# Minimum and maximum number of edges graph with 25 vertices and 6 connected components can have

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.

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}$.
• @MalcolmX: If you’re not familiar with this property of convex functions, note that if $1<a_i<a_j$, then $$(a_i-1)^2+(a_j+1)^2=a_i^2+a_j^2+2(a_j-a_i)+2>a_i^2+a_j^2\;,$$ so you can increase $\sum_ka_k^2$ by decreasing $a_i$ by $1$ and increasing $a_j$ by $1$ without changing $\sum_ka_k$. Doing so repeatedly leads to victorsouza’s solution. – Brian M. Scott Nov 28 '14 at 23:01
• I think you'll find the minimum should be 19, not 20! (Because $\sum_{i=1}^6 (a_i - 1) = \sum_{i=1}^6a_i - 6$, not $\sum_{i=1}^6a_i - 5$.) – Kundor Feb 28 '18 at 23:17