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

2. In a simple graph the number of odd vertices must be even.

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

4. Originally Posted by hmmmm
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???

5. It is impossible to draw a simple graph of order 25 in which all vertices have degree 3.

6. Originally Posted by Plato
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??

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

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

9. Thanks Guys

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

,

,

,

,

# shakehand theorem

Click on a term to search for related topics.