Results 1 to 10 of 10

Math Help - hand shake theorem

  1. #1
    Junior Member
    Joined
    Oct 2007
    Posts
    34

    hand shake theorem

    Hi,

    I was wondering if someone can show me an example similar to this one, so that I can figure this one out for myself?

    The problem is:

    In a group of 25 people, is it possible for each person to shake hands with exactly 3 other people? Explain
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,925
    Thanks
    1764
    Awards
    1
    In a simple graph the number of odd vertices must be even.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Dec 2008
    Posts
    288
    If you consider the people as vertices of a graph, and these vertices are connected if the people shake hands. Then what you want to know is if it is possible to draw a graph with 25 vertices each of degree 3, you now use the handshaking lemma, does this help?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Oct 2007
    Posts
    34
    Quote Originally Posted by hmmmm View Post
    If you consider the people as vertices of a graph, and these vertices are connected if the people shake hands. Then what you want to know is if it is possible to draw a graph with 25 vertices each of degree 3, you now use the handshaking lemma, does this help?
    So are you saying if I can draw a graph with 25 vertices with 3 edges each, this problem is true if not this problem is false???
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,925
    Thanks
    1764
    Awards
    1
    It is impossible to draw a simple graph of order 25 in which all vertices have degree 3.
    See reply #2.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2007
    Posts
    34
    Quote Originally Posted by Plato View Post
    In a simple graph the number of odd vertices must be even.
    Please explain this logic. I don't understand it. Ie: if we have 3 vertices, what has to be even??
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Dec 2008
    Posts
    288
    Well yes but I am not saying that you do it I am then saying you should consider the handshaking lemma and draw a conclusion from that if you can or cannot draw the graph
    The handshaking lemma: Sum of the degree's of all vertices = 2*number of edges

    [Math]\sum\(d_{i}(V)=2*\#E[/tex]
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,925
    Thanks
    1764
    Awards
    1
    It is even easier that that.
    In a simple graph each edge has two vertices.
    The sum of the degrees of the vertices must be an even number.
    If we have 25 odd vertices that sum is 75 which is odd. Impossible.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Oct 2007
    Posts
    34
    Thanks Guys
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Dec 2008
    Posts
    288
    yeah I was putting that because in the title it says handshaking so I thought it was probably look for the handshaking lemma and that the sum of the degree's of the vertices is even is a trivial consequence of the handshaking lemma
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Hand calculation of ! and mod
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 17th 2011, 06:58 PM
  2. Right Hand Derivative and Left Hand Derivative
    Posted in the Calculus Forum
    Replies: 2
    Last Post: August 4th 2009, 06:02 PM
  3. a hand of 13 cards ...
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 30th 2008, 01:36 AM
  4. Hey! I need a hand with this.
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 24th 2008, 09:52 AM
  5. Hand of a Clock
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: September 29th 2008, 10:43 PM

Search Tags


/mathhelpforum @mathhelpforum