A Graph Theorist Walks Into a Bar
One of my new classes this semester is the undergraduate level Introduction to Graph Theory course. I signed up for it with the belief that it would assist me in my future programming endeavors, and I believe it is already paying off. One of the neat things about this class is that it is also the graduate level intro course. The only difference being how much work the students are expected to do (and how much reasoning they are expected to be able to do).
On our first homework assignment the last problem was mandatory for all grad students and was a bonus for everybody else. It was a fun little problem, and I kind of want to walk through how I went about solving it.
Suppose you and your partner attended a party with three other couples. Several handshakes took place. No one shook hands with himself (or herself) and his (or her) partner, and no one shook hands with the same person more than once. After all of the handshaking was complete, suppose you asked each person, including your partner, how many hands he or she had shaken. Each person gave a different answer. How many hands did you shake? Your partner?
This is a graph theory course, so this problem nicely lent itself to being modeled as a graph with each of the vertices representing an individual at the party and each edge representing a handshake between two individuals. Thus the number of hands a person shook during the party was simply the degree of the corresponding vertex.
With the limitation on shaking hands with yourself and your partner, there are only seven possible answers to the question: 6 (shook hands with everyone else), 5, 4, 3, 2, 1, and 0 (shook hands with no one). Since everybody answered uniquely when asked their degree, these were all represented. It also meant that “your” answer was a duplicate of someone else’s.
Looking at the individual with degree 6, I knew that this individual shook hands with everybody at the party except his partner. This meant his (or her) partner could be the only individual with the degree 0. Everybody else had at least one edge going to them thanks to the very-social vertex with degree 6.
I could then do the same with the vertex with degree 5. This individual shook hands with everybody at the party except his partner and the partner with degree 0. The only person who could then have degree 1 would be this vertex’s partner. Now there were only 3 unique answers left, so I just continued with the same logic. The individual with degree 4 had a partner with degree 2. The individual with degree 3 can only have had a partner with degree 3.
I already stated that the vertex with the duplicate degree was “yourself,” so the answer to both questions was: both you and your partner shook three hands.