What a Math Party Game Tells Us About Graph Theory
BIG MOUTH for Quanta Magazine
Introduction
Now that pandemic restrictions are easing up, people are getting together again. But it’s been a while, so if you and your friends need some help breaking the ice, here’s a mathematical party game you can try.
Challenge everyone in your group to shake hands, but only with an odd number of people. (Feel free to substitute air high-fives if you prefer a little more social distance.) Let’s assume it’s you and six of your friends.
At the start, everyone has shaken zero hands, so you all start at an even number. Let’s say Anna and Byron take the initiative and shake each other’s hands. Now they are at one handshake each.
Merrill Sherman/Quanta Magazine
Caitlin needs to join in, so she shakes Byron’s hand, giving her one handshake, an odd number. But now Byron has two handshakes, and so he’s back to an even number.
Demarr, Ernest and Flora jump in and start shaking hands too, flipping even numbers to odds and vice versa.
Eventually your six friends figure things out and arrive at a winning configuration.
But you still have to shake someone’s hand, and that one extra handshake makes a big difference. Once you shake hands, one of your friends will have an even number of handshakes, and now the game must resume.
The picture above shows our game represented as a graph — a collection of points (called vertices) and segments between them (called edges). The dilemma you face exemplifies a simple but profound idea in graph theory, a field of mathematics that studies the properties and features of these important representations. Though many of the fundamental principles of graph theory were established hundreds of years ago, scientists today still use them to better understand how all sorts of systems are connected, from organizations in political networks to animals in ecosystems to websites on the internet. In fact, there’s active research producing new results about the kinds of graphs in our mathematical party game.
In the graph of our game, people are vertices and handshakes are edges. The numbers represent how many handshakes each person has, which in a graph is known as the “degree” of the vertex: It’s the number of edges that are connected to that vertex.
Sample vertices and their degrees.
The graphs that mathematicians study can get very large and complicated, so it helps to have some simple features to look at. One such feature is the sum of all the degrees of a graph. Right away, this “degree sum” tells us that, with seven people, our party game is impossible to win! Let’s see why.
One way to compute the degree sum of a graph is to list all the individual degrees and add them up. But there’s another way that relies on a clever accounting of the edges. Since each edge connects to two vertices, its contribution to the overall degree sum is two: one for each vertex it connects to. So summing all the degrees in a graph is the same as counting every edge twice. Since the degree sum is twice the number of edges, for any graph it always has to be an even number.
This dooms our party game to failure. Think about the graph we’d like to construct to win the game: It must have seven people and seven odd degrees. Now let’s find the degree sum: Add the first two odd degrees and we’ll get an even number. Add the next, and the sum will be odd. Add the next, and the sum will be even, and so on. If you add an odd number of odd numbers, the sum has to be odd. But because the degree sum of any graph must be even, we can’t possibly construct a graph with an odd number of odd degrees. Our party game is unwinnable.
On the other hand, it is possible to win the game if you have an even number of players. We saw this right before it was your turn to shake someone’s hand.
In fact, we saw it even earlier than that: The moment the first two people shook hands.
If only two people play the game, then it’s possible for each of them to shake an odd number of hands. You can think of this pair as an “odd subgraph,” a smaller graph within the larger one whose vertices all have odd degree.
When constructing a subgraph, you pick a set of vertices and consider only the edges between those vertices. This means you just ignore the edges that connect to any vertices outside your subgraph.
Forming subgraphs by ignoring edges.
Forming a subgraph naturally splits a graph into two parts, which is something graph theorists like to do when analyzing a graph: It can help them identify clusters of vertices that are interconnected in special ways. And knowing that a subgraph is even or odd can give additional information about the structure of the graph. For example, an even graph that is “connected” — meaning you can always find a path between any two vertices — must contain an “Eulerian circuit,” a path that passes through every edge exactly once.
From our party game we know that, given a set of vertices, it’s not always possible to form an odd graph. But it is always possible to form an odd subgraph. One boring way to accomplish this is to do what we did above: Just pick two vertices that connect to each other and ignore all their other edges. That makes an odd subgraph, but a very small one. Is it always possible to find a large odd subgraph?
It’s already known that every graph contains a large even subgraph. In the 1960s the Hungarian mathematician Tibor Gallai proved that every graph can be divided into two even subgraphs. Doing this would divide a set of n vertices into two subsets, and one of those subsets would have to contain at least half the vertices. This guarantees that every graph has an even subgraph that’s at least half as big as the original.
But how big an odd subgraph can be has been an open research question in graph theory for over 60 years. In our failed party game graph, there was an odd subgraph that used six of the seven vertices.
This is pretty large relative to the original. But here’s another failed attempt at the game with a smaller maximal odd subgraph, one that uses only four of the original vertices.
A graph with a maximal odd subgraph that uses only four of the seven vertices.
In the search for the largest guaranteed odd subgraph, some early successes expressed the fraction of vertices used in terms of the size of the original graph itself. For example, in the 1990s the mathematician Yair Caro showed that any graph with n vertices must have an odd subgraph that contains at least $latex\frac{1}{\sqrt{n}}$ of the total vertices. This would mean that a graph with 25 vertices must have an odd subgraph that contains at least $latex\frac{1}{5}$ of the 25 vertices, and a graph with 100 vertices would have an odd subgraph that contains at least $latex\frac{1}{10}$ of the 100 vertices. Similar results followed, but mathematicians were looking for what Gallai had found: a single fraction that works for odd subgraphs the way $latex\frac{1}{2}$ works for even subgraphs.
Such a result finally arrived in 2021, when Asaf Ferber and Michael Krivelevich proved that every graph has an odd subgraph that uses at least $latex\frac{1}{10,000}$ of the original graph’s vertices. This may seem like a low bar to set, especially since some have speculated that the true fraction is closer to $latex\frac{2}{7}$, but finding a single fraction that works allows mathematicians to go from proving that such a fraction exists to improving the fraction they already have. One number, like one handshake, can make a big difference.
Exercises
1. Find the largest odd subgraph of the graph shown below.
2. Show how to split the loop below into an odd subgraph and an even subgraph.
3. A complete graph on n vertices is a graph where each of the n vertices is connected by an edge to every other vertex. Could a complete graph be an odd graph?
4. In the 1960s Tibor Gallai proved that it is always possible to split a graph into two even subgraphs. Based on what you’ve read in this column, you can prove that it isn’t always possible to split a graph into two odd subgraphs. What’s the reason?
Click for Answer 1:
Click for Answer 2:
Click for Answer 3:
Click for Answer 4:
