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

Question

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.

Answer 1

I think this adjacency list represents a solution:

1 ->  {}
2 ->  {3, 4, 5, 6, 7, 8}
3 ->  {2, 5, 6, 7, 8}
4 ->  {2}
5 ->  {2, 3, 7, 8}
6 ->  {2, 3}
7 ->  {2, 3, 5}
8 ->  {2, 3, 5}

Note that each even vertex is married to the vertex one less than itself. You are 8.

I kind of intuited the solution. Thought about it for a few minutes and then realized that each couple must have a combined degree of 6 for this to work. Then just figured out how that should work.

What Steven is saying is that you've deduced that there must be a couple with degrees (0,6) and everyone else (1, 2, 3, 4, 5, x). Now consider the subgraph created by removing that first couple. The "husband" didn't shake anyone's hand, so he'll have no effect. The "wife" shook everyone's, so you'll need to subtract 1 from all other degrees. So, you have a graph with (0, 1, 2, 3, 4, x-1), where the same rules apply. From here, you can use the same thought process you used to determine the existence of the (0,6) couple to figure out the existence of a (1,5) couple. It'll actually be (0,4), but you need to add 1 at the end because this is the subgraph not counting the first couple.

Just keep repeating until you're down to someone and the x term, and you should get x = 3.

Answer 2

The nice thing about this problem is you don't really need to solve the graph if you don't want to. You are actually very close. You figured that one couple has multiplicities (6,0). The remainder of the vertices are undifferentiated from each other with respect to the first couple and you have the same rules for that subgraph. So the sub-graph multiplicities are 0,1,2,3,4,x and there is some couple with multiplicities (4,0). That couple has multiplicities (5,1) in the full graph. So as you iterate through the process you will conclude your couples have multiplicities (6,0), (5,1), (4,2), (3,3). And of course you must have multiplicity x=3 so your husband shook 3 hands.