In a simple graph the number of odd vertices must be even.
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
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?
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