How would you solve this graph theory handshake problem in python?

Posted by Zachary Burt on Stack Overflow See other posts from Stack Overflow or by Zachary Burt
Published on 2010-05-25T07:07:38Z Indexed on 2010/05/25 7:11 UTC
Read the original article Hit count: 743

Filed under:

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.

How would you solve this graph theory handshake problem in python?

Posted by Zachary Burt on Stack Overflow See other posts from Stack Overflow or by Zachary Burt
Published on 2010-05-25T06:54:28Z Indexed on 2010/05/25 7:01 UTC
Read the original article Hit count: 743

Filed under:

python

|

math

|

fun

|

graph-theory

|

discrete-mathematics

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.

Developer IT