How would you solve this graph theory handshake problem in python?
- by Zachary Burt
I graduated college last year with a degree in Psychology, but I also took a lot of math for fun. I recently got the book "Introductory Graph Theory" by Gary Chartrand to brush up on my math and have some fun. Here is an exercise from the book that I'm finding particularly befuddling:
Suppose you and your husband attended
a party with three other married
couples. Several handshakes took
place. No one shook hands with himself
(or herself) or with his (or her)
spouse, and no one shook hands with
the same person more than once. After
all the handshaking was completed,
suppose you asked each person,
including your husband, how many hands
he or she had shaken. Each person gave
a different answer. a) How many hands
did you shake? b) How many hands did
your husband shake?
Now, I've been reasoning about this for a while, and trying to draw sample graphs that could illustrate a solution, but I'm coming up empty-handed. My logic is this: there are 8 different vertices in the graph, and 7 of them have different degrees. The values for the degrees must therefore be 0, 1, 2, 3, 4, 5, 6, and x. The # of degrees for one married couple is (0, 6). Since all graphs have an even number of odd vertices, x must be either 5, 3, or 1.
What's your solution to this problem? And, if you could solve it in python, how would you do it?
(python is fun.)
Cheers.
