SOLUTION: Every man on earth has made a certain number of handshakes.Prove that the number of people who have made an odd number of handshakes is even.

Question 3797: Every man on earth has made a certain number of handshakes.Prove that the number of people who have made an odd number of handshakes is even.
Answer by khwang(438) (Show Source): You can put this solution on YOUR website!
This is a basic fact of graph theory.

Every person (not every man !) as a vertex and a handshakes between two
peresons mean the two vertices connecting by an edge in the graph. In
other word, for each edge (handshake) corresponding to two person.)
For each vertex v(person), the number of vertices adjacent to it is
called the degree (# of his/her handshakes).
For any graph G,(ieforany group of people), the summation of deg(v)
for all vertex in G must be equal to 2|E| (where |E| is the number
of edges in G, ie # of handshakes.)

Next among all persons (all vertices in the graph G), some has
odd deg while others are of even degree. But, the # of vertices
with odd degree (odd # of handshakes) should be even. For otherwise,
the total degree of the odd vertices would be odd (why ?). Thus,
adding the even vertices would cause the total degree becoming odd.
This contradicts to the previous claim.
Therefore, the number of people who have made an odd number of handshakes is
even.

Further questions are welcome.
Kenny

RELATED QUESTIONS
There are a number of people in a roo and each person shakes hands once with each of the... (answered by MathLover1)

On a meeting, every guest shakes hands, exactly once, with every other guest. There are... (answered by KMST)

HANNAH MADE SOME BISCUITS FOR A PARTY.sHE PUT THEM ALL OUT ON PLATES.EACH PLATE HAS THE... (answered by Alan3354)

A man has 1044 candles. After burning, he can make a new candle from 9 stubs left behind. (answered by josgarithmetic)

Can you please help my daughter with some homework. It is very late and this is due... (answered by josmiceli)

Prove or disprove algebraically: The sum of an even number and an odd number is... (answered by Alan3354,jim_thompson5910)

To determine whether or not they have a certain disease, 140 people are to have their... (answered by ikleyn)

Eleven groups of people were checking into a hotel. Group one made up 1/4 of the total... (answered by ankor@dixie-net.com)

To determine whether or not they have a certain desease, 204 people are to have their... (answered by Boreal)