0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Nov 28 '14 at 23:01
  • 1
    $\begingroup$ 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$.) $\endgroup$ – Kundor Feb 28 '18 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.