Mathematicians Build Long-Awaited Graph Sandwich - Quanta Magazine

Kristina Armitage/Quanta Magazine

In 2004, two mathematicians hypothesized a powerful kind of sandwich.

They were studying graphs, which are collections of points (called vertices) and lines (called edges). Graphs might represent anything from social groups to the internet to neurons in the brain. The mathematicians hoped to understand properties of one type of graph — a type that’s ubiquitous in mathematics and computer science but difficult to analyze — by sandwiching it, in a mathematically rigorous way, between two simpler graphs.

If researchers could prove the existence of such a sandwich, they wouldn’t just be showing that the middle graph has one property of interest; they’d be showing that it has all sorts of important properties. In doing so, they’d also be demonstrating that two very different random processes that mathematicians like to study are connected in a deeper and more elegant way than they’d imagined.

“The notion is so beautiful,” said Pu Gao (opens a new tab) , a mathematician at the University of Waterloo in Canada who has worked on the problem. “What attracts me most is actually the beauty of it.”

In the past two decades, mathematicians made progress on the “sandwich conjecture,” which says that so long as the graph you’re interested in is large enough, you can always create the needed sandwich. But no one could prove it in full. Then in 2025, three mathematicians found a way to push their field’s techniques to their limits, and completed the quest.

In the late 1950s, the American mathematician Edgar Gilbert was studying telephone networks at Bell Labs. To better understand those networks, he came up with a simple model of a “random” graph, in which vertices connect to other vertices at random. (The mathematicians Paul Erdős and Alfréd Rényi independently came up with a similar model at around the same time.)

To make one of these graphs, start with a set of vertices. Choose any pair of vertices in your set, then flip a (potentially biased) coin. If you get heads, draw an edge between them; otherwise, move on. Repeat this step for every pair of vertices in the graph.

These graphs, known as random binomial graphs, turned out to provide a useful — if imperfect — way to represent networks. They were relatively easy to analyze, and mathematicians proved many interesting things about them. By the 1970s, for instance, they’d discovered under what conditions a random binomial graph will contain a Hamiltonian cycle, a path that visits each vertex exactly once.

But this isn’t the only type of random graph. Mathematicians were also curious about random graphs in which all vertices have the same number of edges. These so-called regular graphs provide a better understanding of random structure than binomial graphs. And they’re often much more accurate at modeling real-world networks.

But because their edges form more constrained, interdependent patterns, they’re also much harder to analyze. It took an additional 20 years of work after the question about Hamiltonian cycles was answered for binomial graphs before mathematicians could do the same for regular graphs.

But what if you can approximate random regular graphs with random binomial graphs? If that’s possible, then mathematicians can get many hard-to-prove properties of a regular graph from the matching binomial graph — for free.

In the early 2000s, Jeong Han Kim (opens a new tab) , then at Microsoft Research, and Van Ha Vu (opens a new tab) , then at the University of California, San Diego, showed how to do this by making a graph sandwich (opens a new tab) .

The idea, loosely stated, was to find a single recipe — a random process — to build a binomial graph and a regular graph at the same time. Not only does this recipe need to generate the right kinds of graphs, but those graphs must also fit together in just the right way. If you can do this, then when you prove results about the binomial graph, which is relatively easy to analyze, those results will also hold for the regular graph.

In the sandwich analogy, it’s like proving things about one of the slices of bread and knowing that those results will also hold true for the cheese in the middle.

But how do those graphs need to fit together, exactly? You have to come up with a recipe that layers the cheese on each slice of bread separately.

First, you need a recipe that gives you a regular graph that contains a binomial graph. That is, the binomial graph’s edges form a subset of the edges that make up the regular graph. If that binomial graph has any property that is more likely to appear when you add edges to it, then your regular graph will also have that property. This is the bottom half of Kim and Vu’s sandwich.

Get Quanta Magazine delivered to your inbox

Similarly, you need a recipe that gives you a regular graph that is contained within a binomial graph. If this bigger binomial graph has properties that are more likely to appear when you remove edges from it, then your regular graph must also have these properties. This is the top half of your sandwich.

Kim and Vu conjectured that so long as your regular graph has a reasonable number of edges, you can almost always build this sandwich (opens a new tab) .

That’s no easy task, given that your recipe needs to create the binomial and regular graphs simultaneously, even though they usually get built using completely different random processes. Over the years, mathematicians proved that the bottom half of Kim and Vu’s sandwich existed, and they proved the upper half in some settings. “It was a sequence of ideas building upon one another,” said Michael Krivelevich (opens a new tab) , a mathematician at Tel Aviv University who has worked on the problem. Each step “requires a very good technique. It requires ingenuity.”

But the sandwich was not yet complete.

The proof of the conjecture would require a way to closely connect the bread and cheese of any sandwich.

In particular, the layers would be built up in tandem, guaranteeing that they would always fit together.

In 2023, three mathematicians — Richard Montgomery (opens a new tab) of the University of Warwick; Natalie Behague (opens a new tab) , his postdoctoral researcher at the time; and Daniel Iľkovič (opens a new tab) , his doctoral student — started to think about ways to build a random regular graph and a random binomial graph edge by edge, ensuring that at each step the regular graph would contain the binomial one. It’s a bit like making your sandwich out of tiny bits of shredded cheese, placing them on the bread one by one, rather than slapping a whole slice on at once.

Richard Montgomery helped craft a recipe for a mathematical sandwich that’s powerful but difficult to make.

To follow their recipe (which, the mathematicians note, is heavily adapted from a 2019 result (opens a new tab) by Gao and two colleagues), start with two sets of vertices without edges. One set will ultimately become your binomial graph, the other your regular graph.

Now build your binomial graph in the usual way. That is, choose a pair of vertices and flip a weighted coin. If your coin lands on heads, add an edge to the binomial graph. Add one to the regular graph as well.

If the coin lands on tails, don’t add the edge in the binomial graph. But you may or may not need to add an edge to the regular graph. After all, a regular graph is defined by the property that every vertex has the same number of edges. You need to make sure that all the required edges are there.

Natalie Behague called the conjecture she recently helped prove “almost too good to be true.”

Kyran O’Brien/Dublin City University

So when your coin lands on tails, ignore your binomial graph, but flip a second weighted coin to decide whether to add an edge to your regular graph. The weight of this second coin will change as you build up your graph. Behague, Iľkovič, and Montgomery came up with a clever way to estimate the weight of the coin as you add more edges to your graphs so that you’re guaranteed to get a truly regular graph. In addition, you also guarantee that your regular graph contains the binomial one, giving you the lower part of the sandwich.

To build the upper part, the mathematicians then reversed their entire process. They began with two graphs that contained every possible edge. They then removed edges one by one until they ended up with a regular graph and a binomial graph that contained it.

They had finished their sandwich. “The conjecture is in some way very natural. It was kind of annoying not to have it proven yet,” Krivelevich said. When he saw the trio’s new result, he was filled with “some kind of relief.”

With the sandwich conjecture resolved, mathematicians no longer have to prove every property of random regular graphs from scratch. They can now draw on the vast literature that’s been written about random binomial graphs and get all sorts of properties automatically.

That means they can rewrite scores of results about regular graphs in a single, streamlined proof. And new results are already starting to appear (opens a new tab) .

Moreover, the proof of this “meta-theorem,” as Gil Kalai (opens a new tab) of the Hebrew University of Jerusalem put it, offers a set of methods that “enriches our toolbox” and “sharpens our technical teeth.” Those methods might allow mathematicians to understand even more about the structure of networks than they originally set out to.

In the meantime, researchers hope to make even more complicated sandwiches, filled with alternating layers of binomial and regular graphs, or with other ingredients. In doing so, they’re continuing to explore the ways in which seemingly different random processes — one very constrained, the other not — are more similar than they look. “That sort of deep connection between the two,” Behague said, “seems almost too good to be true.” And yet it is.

Get Quanta Magazine delivered to your inbox

Get highlights of the most important news delivered to your email inbox

Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation. Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected. Moderators are staffed during regular business hours (New York time) and can only accept comments written in English.