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