15
$\begingroup$

Let $m$ be the number of edges, $n$ the number of vertices and $k$ the number of connected components of a graph G.

Prove that:

$m$ $\leq$ $\frac{(n-k+1)*(n-k)}{2}$

Thanks!

$\endgroup$
  • $\begingroup$ Try to find "the most extreme" situation. $\endgroup$ – Jihad Dec 20 '14 at 16:36
  • $\begingroup$ I know that this is true since I write some examples of those extreme situations. Nevertheless, I couldn't find a way to prove this in a formal way, which is what I need to do. $\endgroup$ – Federico Martinez Dec 20 '14 at 16:41
  • 1
    $\begingroup$ If you remove vertex from small component and add to big component, how many new edges can you win and how many you will loose? $\endgroup$ – Jihad Dec 20 '14 at 16:48
13
$\begingroup$

The maximum number of edges is clearly achieved when all the components are complete.

Moreover the maximum number of edges is achieved when all of the components except one have one vertex. The proof is by contradiction. Suppose the maximum is achieved in another case. Then there exist two components with more than one vertex say the number of vertices are $n$ and $m$ . Pick the one with the less vertices suppose it is $m$ vertices. Take one of it vertices and delete it. removing $m-1$ edges. now add a new vertex to the component with $n$ vertices and join it to all its vertices, adding $n$ edges. This graph has more edges, contradicting the maximality of the graph.

Hence the maximum is achieved when only one of the components has more than one vertex. How many vertices does this graph have? the big component has $n-k+1$ vertices and is the only one with edges. So it has $\frac{(n-k+1)(n-k)}{2}$ edges.

$\endgroup$
  • $\begingroup$ thanks thats nice, clean and logical proof. I came across another one which I dont understand completely. Can you help me to understand? I have put it as an answer below. $\endgroup$ – anir123 Sep 27 '15 at 9:39
  • $\begingroup$ @hardmath Got it, I'll do that next time $\endgroup$ – evaristegd May 19 '18 at 1:05
3
$\begingroup$

Below is the proof replicated from the book by Narsingh Deo, which I myself do not completely realize, but putting it here for reference and also in hope that someone will help me understand it completely. Things in red are what I am not able to understand.

Proof

Let the number of vertices in each of the $k$ components of a graph G be $n_1,n_2,...,n_k$. Thus we have,

$$n_1+n_2+...+n_k=n$$ $$n_i\geq 1$$

The proof of the theorem is based on the inequality $$\sum^k_{i=1}n_i^2\leq n^2 -(k-1)(2n-k)$$

This inequality can be proved as follows.

$$\sum_{i=1}^k(n_i-1)=n-k$$ Squaring both side, $$\left(\sum_{i=1}^k(n_i-1)\right)^2=n^2+k^2-2nk$$ or $$\color{red}{\sum_{i=1}^k(n_i^2-2n_i)+k+\text{nonnegative cross terms}= n^2+k^2-2nk}$$

because $(n_i-1)\geq 0$, for all $i$.

Therefore, $$\color{red}{\sum_{i=1}^kn_i^2\leq n^2+k^2-2nk-k+2n=n^2-(k-1)(2n-k)}$$

Thus the required inequality is proved.

Now the maximum number of edges in $i^{th}$ component of G (which is simple connected graph) is $\frac{1}{2}n_i(n_i-1)$. Therefore, the maximum number of edges in $G$ is

$$\frac{1}{2}\sum^k_{i=1}(n_i-1)n_i=\frac{1}{2}\left( \sum_{i=1}^kn_i^2 \right) - \frac{n}{2}$$ $$\leq \frac{1}{2} \left( n^2-(k-1)(2n-k) \right) - \frac{n}{2}$$ $$=\frac{1}{2}(n-k)(n-k+1)$$

$\endgroup$
  • $\begingroup$ what part are you having trouble with? $\endgroup$ – Jorge Fernández Hidalgo Sep 27 '15 at 14:15
  • $\begingroup$ ohh I simply forgot to tell that red are the the ones I am not able to understand $\endgroup$ – anir123 Sep 27 '15 at 14:44
  • 1
    $\begingroup$ Oh ok. Well, he has the equality $(n_1-1)+(n_2-1)+(n_3-1)+\dots (n_k-1)=n-k$. So if he squares both sides he has: $((n_1-1)+(n_2-1)+(n_3-1)+\dots (n_k-1))^2=n^2+k^2-2nk$. But how do you square a sum? you have to use the distributive law right? You have to take the multiplication of every pair of elements and add them. What the author is doing is separating the sum in two parts, the squares of each element $n_i^2$ plus the products of $n_in_j$ with $i\neq j$. So he gets $((n_1-1)^2+(n_1-1)^2+\dots +(n_k-1)^2)+Other part =n^2+k^2-2nk$. $\endgroup$ – Jorge Fernández Hidalgo Sep 27 '15 at 14:55
  • 1
    $\begingroup$ So $(n_1^2-2n_1+1)+(n_2^2-2n_2+1)+\dots (n_k^2-2n_+1)+other part=(n_1^2-2n_1)+(n_2^2-2n_2)+\dots + (n_k^2-2n_k)+k+otherpart=n^2+k^2-2nk$ as desired. $\endgroup$ – Jorge Fernández Hidalgo Sep 27 '15 at 14:56
  • $\begingroup$ Also notice that "Otherpart" is not negative since all of its summands are positive as $n_i\geq 1$ for all $i$. $\endgroup$ – Jorge Fernández Hidalgo Sep 27 '15 at 14:58
0
$\begingroup$

I've answered the OP's specific question as to how the book's proof makes sense. I haven't given the complete proof in my answer. I have just explained the steps marked in red, in @Mahesha999's answer. Thus, this is just an elaborate extension of @Mahesha999's answer.


A more detail look into the algebraic proof.

Assuming $n_1 + n_2 + ... + n_k = n$ and $n_i \geq 1$, the proof from the book uses the following algebraic identity to solve the problem:

$$\sum^k_{i=1}n_i^2\leq n^2 -(k-1)(2n-k) \;\;\;\;\;...(1)$$

At a first glance, what happens internally might not seem apparent. The proof for the above identity follows from expanding the following expression.

$$\left(\sum_{i=1}^k(n_i-1)\right)^2=n^2+k^2-2nk \;\;\;\;\;...(2)$$

The choice of using the term $(n_i - 1)$ follows directly as $n_i \geq 1$ or $n_i - 1 \geq 0$. This is a maximization problem, thus, the problem must either be solved by maximizing a positive term (or trying to equate a part of it to zero) or by minimizing a negative term. Note that $n$ is assumed to be a constant, but we are free to vary the distribution of the number of vertices in each of the components in the graph; thus we are free to vary the values taken by $n_1, n_2, ..., n_k$ as long as their sum remains equal to $n$. (2) can be written as,

$$\sum_{i=1}^k(n_i^2-2n_i)+k+\sum_{i, j \in [1, k], i \neq j}((n_i - 1)(n_j-1))= n^2+k^2-2nk \;\;\;\;\;...(3)$$

The positive terms that are neglected are, $$\sum_{i, j \in [1, k], i \neq j}((n_i - 1)(n_j-1))\;\;\;\;\;...(4)$$

I was reading the same book and I had the same problem. Fortunately, I was able to understand it in the following way. If simply removing the positive terms was enough, then it is possible to write,

$$\sum_{i=1}^kn_i^2 < n^2-(k-1)(2n-k)$$

But claiming

$$\sum_{i=1}^kn_i^2 \leq n^2-(k-1)(2n-k)$$

Requires us to have ways for convincing ourselves that the value of $\sum_{i=1}^kn_i^2$ can become equal to $n^2-(k-1)(2n-k)$ for some values of $n_i$.

The RHS in (3) fully involves constants. Thus, its value is bound to remain static. Is it possible to vary the values of $n_i$, as long as its sum equals $n$. Hence to maximize the value of the term $\sum_{i=1}^kn_i^2$ (which is our ultimate goal), we must minimize the value of the term (4), all the while ensuring that the sum $\sum n_i$ equals $n$. Doing this will maximize $\sum_{i=1}^kn_i^2$ because, the RHS does not change as $n$ and $k$ are fixed; thus, out of the two terms present in the LHS, reducing the value of (4) must increase the value of the term $\sum_{i=1}^kn_i^2$. Maximizing the term $\sum_{i=1}^kn_i^2$ eventually causes the summation $\frac{1}{2}\sum^k_{i = 1}(n_i (n_i-1))$ to be maximized leading us to the result.

Thus we must just show that (4) can be equated to $0$, with the value of the summation $\sum(n_i)$ still being equal to $n$.

$$\sum_{i = 1}^k \sum_{j = i + 1}^k (n_i - 1)(n_j-1) = 0, \sum_{i = 1}^k n_i = n ...(5)$$

For a constant $ 1 \leq c \leq k $, let's assign $n_c = n- k$ and for all values of $i$, with $i \neq c$, assign $n_i = 1$. As every term $(n_i - 1)$ in (4) has every other term $(n_j - 1)$ (with $i \neq j$ ) as a coefficient. Thus all terms reduce to zero. This it has been established that (4) can take the value zero. But the RHS remains the same; hence to compensate for the loss in magnitude, the term $\sum_{i=1}^kn_i^2$ get maximized.

Hence we have shown the validity of (5). Thus, we can write (3) as,

$$\sum_{i=1}^k(n_i^2-2n_i)+k+\sum_{i, j \in [1, k], i \neq j}((n_i - 1)(n_j-1))= n^2+k^2-2nk$$

or,

$$\sum_{i=1}^k(n_i^2-2n_i)+k \leq n^2+k^2-2nk \;\;\;\;\;...(6)$$

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