Thread: Problem 29
View Single Post
  #4  
Old July 2nd, 2007, 04:23 AM
galactus's Avatar
galactus galactus is offline
Eater of Worlds

  
Join Date: Jul 2006
Location: Chaneysville, PA
Posts: 2,883
Country:
Thanks: 121
Thanked 1,105 Times in 993 Posts
galactus has much to be proud ofgalactus has much to be proud ofgalactus has much to be proud ofgalactus has much to be proud ofgalactus has much to be proud ofgalactus has much to be proud ofgalactus has much to be proud ofgalactus has much to be proud ofgalactus has much to be proud of
Default
Quote:
1)In a room let there be n>1 people. Show that there must exist two people that shaked the same number of hands with others.
I was thinkin', PH, maybe we could make this a graph theory problem and call a person a vertex and a handshake an edge. Is that your approach?.

I am certainly no expert graph theorist, but you can't have a graph with n vertices with a vertex having 0 degrees and another have n-1 degrees. So, therefore, hence, and heretofore, the most degrees the vertices can have is n-1 degrees. But since there's n vertices/vertexes, at least 2 have the same degree.

I even drew a little graph to picture the handshakes.

If I'm not right, I suppose I'll be wrong.