Results 1 to 11 of 11

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

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    10

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

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    Hello and welcome to the forum.

    how does the rounded step came in the following image???
    Did you forget to attach the image?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2011
    Posts
    10
    sorry sir.. now i have attached the image...

    http://images.elektroda.net/88_1304862170.png
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    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<j\le k}n_in_j, so it is sufficient to show that 2\sum_{1\le i<j\le k}n_in_j\ge (k-1)(2n-k).

    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<j\le k}n_in_j\ge (k-1)(2n-k) 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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2011
    Posts
    10
    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??
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    What do you mean, "how this (k-1)(2n-k) came"?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    May 2011
    Posts
    10
    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..
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    May 2011
    Posts
    10
    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..
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    May 2011
    Posts
    10
    thank you.. now its clear.. thanks for spending ur valuable time with me..
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  2. proof of cayley's theorem; graph theory
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 15th 2011, 09:21 AM
  3. Replies: 1
    Last Post: September 26th 2010, 09:53 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory [Menger's Theorem]
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 27th 2008, 01:29 PM

Search Tags


/mathhelpforum @mathhelpforum