Results 1 to 2 of 2

Math Help - Graph theory Proof - shaking hands

  1. #1
    Newbie
    Joined
    Aug 2010
    Posts
    8

    Graph theory Proof - shaking hands

    I have a proposition that says in a group of 25 people, it is possible for each to shake hands with exactly with 3 other people. I am pretty sure that it is true and that I have to use a directed graph to prove it but I don't know where to go after that. Can anyone give me a hint? Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member MacstersUndead's Avatar
    Joined
    Jan 2009
    Posts
    291
    Thanks
    32
    Quote Originally Posted by learningguy View Post
    I have a proposition that says in a group of 25 people, it is possible for each to shake hands with exactly with 3 other people. I am pretty sure that it is true and that I have to use a directed graph to prove it but I don't know where to go after that. Can anyone give me a hint? Thanks in advance.
    Recall the Handshaking Lemma. Can a simple graph be drawn with 25 vertices all with degree 3? If this were the case, the sum of all the degrees would 75, an odd number. What's wrong with this?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 11th 2010, 11:00 PM
  2. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 7th 2010, 11:59 AM
  3. Graph theory proof
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: May 6th 2010, 05:27 AM
  4. Graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 26th 2009, 09:01 PM
  5. Graph Theory Proof please:-
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 18th 2008, 03:06 PM

Search Tags


/mathhelpforum @mathhelpforum