“It was a big surprise to me that it turned out to be true,” Seymour said. “There didn’t seem to be any reason for it to be true.”
Combing for Results
To reach their unexpected result, the team relied upon the classic technique of “proof by contradiction.” They assumed that there is a counterexample to the conjecture — a graph that does not contain a five-cycle anywhere but also does not have a sufficiently large clique or stable set, in defiance of Erdős-Hajnal. “We then tried to prove so many things about it that it can’t possibly exist,” Seymour said. And if the counterexample could not exist, that meant the conjecture must have been right in the first place.
The actual argument, of course, is more involved. The team wasn’t interested in just any counterexample — they sought the smallest possible one, which is a common tactic in graph theory, Spirkl said. Mathematicians often find minimal counterexamples easier to work with because they can focus on those parts of the graph that are relevant to the problem at hand and temporarily ignore the rest.
“The smallest counterexample has the property such that if I delete a single vertex, then it suddenly is not a counterexample anymore,” Spirkl said. The remaining graph, which has been reduced from n to n – 1 vertices, now has a clique or stable set that’s so big it no longer qualifies as a counterexample.
The five-cycle proof also built on a 2020 paper from Pach and István Tomon that presented a method for finding certain structures called “combs” in a graph.
To get a sense of what these combs look like, imagine a graph that contains something resembling a simple, wide-tooth comb with the teeth pointing upward. Let’s also assume there is a vertex directly above the comb, along with edges that connect it to the tips of all teeth. The object we’ve just described is similar to a comb in the mathematical sense: There, at the base of each tooth, lies a string of vertices that may have edges between them.
If we look more closely at the edge between two such vertices, we can follow a path from that base up through the two parallel teeth (each constituting an edge). From there, we connect the tips of the teeth via separate edges to the single vertex above the comb, and the shape we’ve just traced out is actually a five-sided polygon.
In their new paper, Chudnovsky and her colleagues refined Pach and Tomon’s method to show that every smallest counterexample contains, somewhere within it, a large comb. That implies that it must have a five-cycle — the one thing it’s not supposed to have. And of course, that means it’s not a counterexample at all. By showing that no counterexample to the conjecture could be found, the four collaborators proved that the conjecture must be true in this case.
A Route to the Summit?
Now that the five-cycle question is answered, could it lead to a proof of the full conjecture, as Erdős and Hajnal anticipated? “For a long time, the five-cycle seemed just as hard as the general question,” Seymour said. “The hope was that if we could do that, we could do the general question. But that hope has fizzled a bit.”
“This proof doesn’t nearly bring us there,” Spirkl confessed. “At the moment it seems that we would need some significant new ideas.” But there is hope, she added. “It may be the first of a long series of steps.”
“Solving the five-cycle case makes more people think that the general conjecture must be true,” Graham said. “Although no one has found a way to prove it yet, having a success like this helps spread the word.”
Even on its own, the proof is still considered a major accomplishment — the biggest development concerning this conjecture in more than a decade, and one whose results are not solely limited to the five-cycle case. “The techniques they were forced to develop to solve this problem can be applied to other problems,” said Chvátal, “which is how we make progress in mathematics.”
The four co-authors have already begun this process, proving in the same paper that the Erdős-Hajnal conjecture holds for other special cases, including the so-called five-cycle with a “hat” — a six-cycle with an extra edge that joins two vertices, forming a pentagon with a triangle (or hat) on top.
