Results 1 to 7 of 7

Math Help - Vertices of a simple graph

  1. #1
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2

    Vertices of a simple graph

    Prove that a smiple graph with at least two vertices would have two or more vertices of the same degree.

    thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Realize that if a simple graph has n vertices then the maximum degree of any vertex is n-1. Thus suppose that we have a simple graph G with a degree sequence of <0,1,2,…,n-1>, that is all the n-vertices are of different degree. Now remove the vertex of degree 0. We now have a new graph G’ with (n-1) vertices and the same number of edges. But it has a vertex of degree (n-1). But that is impossible; so the original graph is impossible. Thus the graph G would have to have at least two vertices of the same degree.
    Last edited by Plato; May 24th 2007 at 04:23 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2007
    Posts
    8

    Discrete maths solutions - option?

    TTcommander

    Thanks heaps for your explanations.


    By the way what is the option of using the "piegonhole" principle of answering the question - 2nd form.


    Looking forward to your comments.

    Thanks

    Fortuna
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Apr 2007
    Posts
    8

    Sorry for getting the name wrong my apology Plato

    Plato

    By the way what is the option of answering the question using the pigeonhole princple - 2nd form? Look forward to your comments.

    Cheers

    Fortuna
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by fortuna View Post
    Pluto
    Thanks heaps for your explanation on Q. 2.
    Quote Originally Posted by Jhevon View Post
    It's "Plato", lol
    Itís a dogís life is it not.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by fortuna View Post
    By the way what is the option of answering the question using the pigeonhole principle - 2nd form?
    Actually the graph theory proof above does use the pigeonhole principle implicitly. Think of 15 pigeonholes numbered 0,1,2,…,14. Assign each person to the hole that matches the number of acquaintances at the meeting that he/she has. If the hole #14 is empty then the fifteen will be assigned to 14 holes so there is a hole 0-13 with at least two. If hole #14 is not empty then someone there knows each other person there. Hence hole #0 must be empty(WHY?) Thus the fifteen will be assigned to 14 holes so there is a hole 1-14 with at least two.
    Last edited by Plato; June 8th 2007 at 02:48 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2007
    Posts
    8

    Question 2 - Thanks

    Plato

    Your explanation makes good sense.
    Thanks heaps.

    Cheers

    Fortuna
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Vertices pairwise in grid graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 13th 2009, 07:41 AM
  2. colouring vertices in graph theory
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 3rd 2009, 03:53 PM
  3. Replies: 0
    Last Post: October 5th 2009, 05:54 PM
  4. how many vertices does this graph have.....
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 27th 2008, 06:30 PM
  5. Replies: 5
    Last Post: January 14th 2007, 02:55 PM

Search Tags


/mathhelpforum @mathhelpforum