New Proof Reveals That Graphs With No Pentagons Are Fundamentally Different

If the Erdős-Hajnal conjecture is true, then graphs with forbidden induced subgraphs behave very differently from general graphs, according to Maria Chudnovsky of Princeton University. “It tells you that if you provide me with some very local information about the graph — information regarding a small number of vertices — then something global happens. If I forbid a certain small structure, then a huge structure will inevitably emerge.”

The global consequences of local restrictions is a common theme in graph theory, said Timothy Gowers of the University of Cambridge. But “like many other conjectures that are relatively simple to state but surprisingly hard to solve, [this conjecture] seems to expose a gap in our understanding.”

Now, in a February 2021 paper, Chudnovsky, Alex Scott of the University of Oxford, Paul Seymour of Princeton University and Sophie Spirkl of the University of Waterloo have made huge progress toward filling in that gap. They didn’t prove the whole conjecture, but they showed that it holds true for a critical induced subgraph singled out by Erdős and Hajnal. “We were all a little shocked,” Chudnovsky said. “We thought this would be the case that was false, and the conjecture would fall.”

Gowers called the work “exciting,” and Vašek Chvátal of Concordia University said, “A number of good people have tried very hard over the years to solve this problem.”

“This is a major result in graph theory,” added Fan Chung Graham, a mathematician at the University of California, San Diego.

Slow Progress

Although the Erdős-Hajnal conjecture is “fundamental and fascinating,” said Chvátal, proving it has turned out to be extremely difficult. So far, mathematicians have attacked it on a case-by-case basis, mostly starting with the smallest prohibited structures and moving up from there.

But progress has been slow, with major results emerging about once every decade or two. That means the conjecture has only been confirmed in a handful of instances to date, including all those in which the excluded induced subgraph has four vertices or fewer.

In 2005, Chudnovsky and Shmuel Safra of Tel Aviv University proved that the Erdős-Hajnal conjecture was upheld when the forbidden induced subgraph is a five-vertex structure known as the bull, which resembles an inverted triangle with two single-vertex horns on top. That left only two five-vertex configurations still open: the pentagon (or really any five-sided polygon), also called a five-cycle, and the five-vertex path, which consists of four line segments linked together, forming an open chain.

Of the two outstanding problems, the five-cycle was the more prominent, because of the elevated status granted it by Erdős and Hajnal, and consequently by everyone else. “They thought that it was complicated enough that if you could settle that case, you could settle the conjecture for all cases,” said János Pach of the Rényi Institute of Mathematics in Budapest, who collaborated with both Erdős and Hajnal.

Hajnal, among others, suspected that the conjecture would ultimately turn out to be false. And when he first started on this project, Seymour would have agreed. He thought the five-cycle case, in particular, would be the counterexample demonstrating that very point. But instead, the opposite occurred: He and his co-authors showed that barring this particular induced subgraph from a graph would invariably produce either a large clique or a stable set, exactly as prescribed by the Erdős-Hajnal conjecture.

“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.

But there is one induced subgraph in particular that many mathematicians have in their sights. “The five-vertex path has to be next,” Seymour said. “If you can’t do that, you’re still nowhere.”

“There are definitely ideas from the five-cycle proof that seem useful for the five-vertex path,” Spirkl said, “but they wouldn’t take us all the way there.”

Given that, at present, no one knows how to attack the conjecture as a whole, the only available option, Chudnovsky said, is “approaching this problem one case at a time. We do what we can do.”

And of course, there’s always the chance that this piecemeal approach could yield a big payoff. “One reason we’re doing these special cases is that they might lead us to a counterexample,” said Seymour, which would show that the conjecture is false.

Thirty-two years after it was first published, the Erdős-Hajnal conjecture has turned out to be “a surprisingly treacherous peak,” said Pach. “Chudnovsky, Scott, Seymour and Spirkl have settled this special case, but we still don’t know where we stand. From our present location, we cannot see the summit. Perhaps we are almost there. Perhaps we are less than halfway. We have to wait for the fog to lift.”