It’s always quite a pleasant surprise whenever some random situation ends up tying back into graph theory. One particular scenario I recently read about is a group of 7 friends deciding to have a party due to COVID-19 restrictions being somewhat lifted. They get the idea to see if each one of them can shake hands with an odd number of people among the other 6. This quickly caught my attention due to the resemblance to the famous graph theory problem regarding the Seven Bridges of Königsberg (briefly mentioned in lecture), in which it was asked if it was possible to cross all 7 bridges exactly once. Both scenarios involve the number 7, as well as a question of whether it was possible to perform a certain action. They also share many other similarities, which I will discuss later.
For the bridges problem, a graph can be made based on the shape of the city and the arrangement of the bridges:
It is natural for many to try to manually find a solution by brute-forcing the various possible paths. Likewise in the party problem, they can try to manually find a solution by drawing a graph, beginning with 7 nodes representing the partygoers and then adding edges in different ways, hoping one way would yield a solution. Some might even start with 6 nodes, with the missing node to be drawn later, representing someone who will eventually make the final move. Let’s consider one such attempt. Here, the first handshake begins:
C makes their move, and randomly decides to shake hands with B:
D, E, and F then decide to join in:
With more handshakes, the 6 all get odd numbers of handshakes:
But then the 7th person has to come in and shake someone’s hand, and all of a sudden someone has an even number again:
Well that didn’t work. Is there a different sort of attempt that may work? Unfortunately, the answer is no. Fortunately, there is a quick way to figure out this fact. Let’s first look at the similar method for the bridges problem. For any graph without self-loops, consider a start vertex S and an end vertex V (the two may be the same vertex or not). For any path from S to V without reusing edges, all intermediate nodes must have an even degree, since every time you enter each one with a new edge, you must leave it with another new edge. So in the graph representing Königsberg, to use each of the 7 edges exactly once, no more than 2 of the 4 nodes can have an odd degree. Yet all 4 nodes have an odd degree, so there is no way to use all 7 edges exactly once.
The way to prove there is no solution to the party problem is similar, in the sense it shows that a solution requires a particular condition to pass, but since this condition fails, there is no solution. It even involves odd numbers being a big deal, like in the bridges problem! Here, we consider the fact that in every graph without self-loops, the degree sum is an even number. This is because each edge is counted twice, as it is associated with 2 nodes. So in particular, the graph representing the solution to the party problem should have an even degree sum. But 7 people each having shaken hands with an odd number of people out of the other 6 would be represented by 7 nodes all of odd degree, and adding an odd number of odd degree numbers gives an odd degree sum, not an even one! This contradiction means there really is no solution.
With all the similarities between the really old bridges problem and this recent party one, I wonder if the latter was deliberately based off of the former. Nevertheless, the fact that both real-life situations, along with many others, can be solved with graph theory shows how powerful and useful it really is in everyday life.
Sources:
https://www.quantamagazine.org/what-a-math-party-game-tells-us-about-graph-theory-20220324/
https://medium.com/stamatics-iit-kanpur/the-seven-bridges-of-k%C3%B6nigsberg-268f73122e82