1
$\begingroup$

What is the biggest number of components in a graph that has 14 vertices and 44 edges?

Since total degree of all vertices in a graph equals to 2 * number of edges, I calculated that for 44 edges, 14 vertices together must have 88 degrees. 88 / 14 = 6, therefore each of them would have to be connected to other 6 vertices and we would still have 4 edges left. So, the only solution I see is using a full graph K10, where we'd have 90 edges ((n*(n-1))/2). We'd use 10 vertices and eliminate 2 edges. And the rest 4 vertices we would leave isolated, so we'd get 5 components all together.

$\endgroup$
  • 1
    $\begingroup$ Try turning your intuition to a proof. $\endgroup$ – Yuval Filmus Dec 1 '17 at 16:05
  • $\begingroup$ Is my intuition even correct? I don't know how to turn it into a proof.. $\endgroup$ – Maria Dec 2 '17 at 11:23
  • 1
    $\begingroup$ The way to check whether your intuition is correct is via proof. $\endgroup$ – Yuval Filmus Dec 2 '17 at 15:03
  • $\begingroup$ Could you give me an example or a hint as to how to formulate the proof? $\endgroup$ – Maria Dec 3 '17 at 8:44
  • 1
    $\begingroup$ Try solving some similar problems with smaller numbers, and see if you can generalize. $\endgroup$ – Yuval Filmus Dec 3 '17 at 12:27
1
$\begingroup$

Suppose that a graph having $n$ vertices and $m$ edges consists of $k$ connected components, say of sizes $n_1,\ldots,n_k$. Then $$ m \leq \binom{n_1}{2} + \cdots + \binom{n_k}{2}. $$ Conversely, given $n_1,\ldots,n_k$ summing to $n$ which satisfy this inequality, we can construct a graph with $n$ vertices, $m$ edges, and at least $k$ connected components. We conclude that the maximum number of connected components of a graph with $n$ vertices and $m$ edges is the maximal $k$ such that we can find $n_1,\ldots,n_k \geq 1$ summing to $n$ satisfying the inequality above.

This leads to the following question: given $k$, maximize $\binom{n_1}{2} + \cdots + \binom{n_k}{2}$ subject to the constraint that $n_1,\ldots,n_k \geq 1$ are integers summing to $n$. The key is the following observation: $$ \binom{a+1}{2} + \binom{b-1}{2} - \binom{a}{2} - \binom{b}{2} = a-b+1. $$ This shows that as long as $n_i \geq n_j$, moving a vertex from $n_j$ to $n_i$ increases $\binom{n_i}{2} + \binom{n_j}{2}$. It follows that the choice of $n_1,\ldots,n_k$ maximizing $\binom{n_1}{2} + \cdots + \binom{n_k}{2}$ is $n_1=n-k+1$, $n_2=\cdots=n_k=1$.

We have proved: the maximal number of connected components of a graph with $n$ vertices and $m$ edges is the maximal $k$ such that $$ m \leq \binom{n-k+1}{2}. $$

$\endgroup$

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.