Mathematicians Build Long-Awaited Graph Sandwich

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

Graphs of Different Flavors

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, then at Microsoft Research, and Van Ha Vu, then at the University of California, San Diego, showed how to do this by making a graph sandwich.

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.