# Math Help - a theorem in graph theory.. please help

1. ## a theorem in graph theory.. please help

how does the rounded step came in the following image??? please help... i am new to this forum.. please forgive if anything is wrong..

2. Hello and welcome to the forum.

how does the rounded step came in the following image???
Did you forget to attach the image?

3. sorry sir.. now i have attached the image...

http://images.elektroda.net/88_1304862170.png

4. Interesting... I think I came up with a proof, but it is way too complicated.

We need to show that $\sum_{i=1}^k n_i^2\le n^2-(k-1)(2n-k)$. The left-hand side is $n^2-2\sum_{1\le i, so it is sufficient to show that $2\sum_{1\le i.

The following statement can be proved by induction on k: For every sequence $n_1,\dots,n_k$ where each $n_i\ge 1$ (and, therefore, $k\le n$), we have $2\sum_{1\le i where $n=n_1+\dots+n_k$.

However, I am really wondering if there is an easier way.

If you need more details, feel free to ask.

Edit: If you don't mind, where does this proof come from?

5. thank you sir.. i took this proof from "Combinatorics and Graph Theory " by C. Vasudev ... can you please tell me how this (k-1)(2n-k) came??

6. What do you mean, "how this (k-1)(2n-k) came"?

7. i am just asking abt the conventional method... we will take LHS , solve it and get the RHS... that's why i asked the question "how this (k-1)(2n-k) came"?.. if wrong pls forgive..i am little confused..

8. Above, I indicated the steps to prove $\sum_{i=1}^k n_i^2\le n^2-(k-1)(2n-k)$. The key lemma is proved by induction. If you have questions about these particular steps, including the proof by induction, feel free to ask, but your questions have to be more specific.

The proof suggested above looks too complicated for the transition from one line to the next in the original post. On the other hand, some authors sometimes do take out a whole page of calculations and replace it with the words, "It is obvious that..." I would really like to know if this is the case here.

9. let me assume n=k..in such case each component will have 1 vertex.. then will 2\sum_{1\le i<j\le k}n_in_j\ge (k-1)(2n-k) hold good??? please forgive me.. these questions may be silly.. but these blast my head..

10. If n = k, then each term $n_in_j$ in the sum in the left-hand side is 1. There are ${n\choose 2}=n(n-1)/2$ terms in the sum, so the left-hand side is n(n - 1). It is easy to see that the right-hand side also equals (n - 1)n.

11. thank you.. now its clear.. thanks for spending ur valuable time with me..