Mathematicians Build Long-Awaited Graph Sandwich

Graph sandwich, a concept mathematicians have chased for more than twenty years, is finally complete. In 2004, two researchers hypothesized that a powerful kind of mathematical sandwich could always be built around certain difficult graphs. In 2025, three mathematicians proved them right.

What a Graph Sandwich Actually Is

Graphs are collections of points called vertices and lines called edges. They can represent almost anything: social groups, the internet, neurons in the brain. Mathematicians wanted to understand one type of graph that shows up everywhere in mathematics and computer science but resists analysis. Their solution was to trap it, in a rigorous way, between two simpler graphs. That is the graph sandwich.

If researchers could prove such a sandwich exists, they'd show something far bigger than one property of interest sitting inside the middle graph. They'd show it all at once. It's got every important property. And they'd also demonstrate that two very different random processes are connected more deeply than anyone had imagined, a link nobody saw coming and that reshapes what we've assumed about both of them.

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

Two Flavors of Random Graph

It starts in the late 1950s. Edgar Gilbert was an American mathematician. He worked at Bell Labs, where he studied telephone networks, and while he was there he devised a simple model of a random graph in which vertices connect at random. Paul Erdős and Alfréd Rényi independently came up with something similar around the same time.

To build one of these graphs, you start with a set of vertices. Choose any pair, flip a potentially biased coin. Heads means draw an edge between them. Tails means move on. Repeat for every pair. These random binomial graphs proved useful, if imperfect, for representing networks. They were relatively easy to analyze, and by the 1970s mathematicians had figured out under what conditions one would contain a Hamiltonian cycle, a path that visits each vertex exactly once.

But there is another type. Mathematicians were also curious about random graphs in which every vertex has the same number of edges. These regular graphs model real-world networks more accurately and reveal random structure better than binomial graphs do. Their edges form more constrained, interdependent patterns, which makes them far harder to analyze. It took an additional twenty years after the Hamiltonian cycle question was settled for binomial graphs before mathematicians could answer the same question for regular graphs.

The Promise of Approximation

What if you could approximate random regular graphs with random binomial graphs? That's the question. And it's a big one. Because if you can, then hard-to-prove properties of a regular graph could be borrowed from the matching binomial graph, and they're free, meaning you don't have to prove them yourself, since the work is already done for you. So you get them for free.

In the early 2000s, two researchers made a strange bet. 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, which is exactly what it sounds like. The idea was to find a single recipe, a random process, that builds a binomial graph and a regular graph at the same time. And the recipe can't just work. It must generate the right kinds of graphs, and those graphs must fit together in just the right way, which means they're locked into a structure that leaves no room for error.

The fit has two halves. First, you need a recipe that gives you a regular graph containing a binomial graph, meaning the binomial graph's edges form a subset of the regular graph's edges. If the binomial graph has a property that becomes more likely when you add edges, the regular graph has it too. That is the bottom half. Second, you need a regular graph contained within a binomial graph. If the bigger binomial graph has properties that become more likely when you remove edges, the regular graph must have them too. That is the top half.

Kim and Vu conjectured this. Build the sandwich. So long as your regular graph has a reasonable number of edges, you can almost always do it, which is the claim they put forward. That was no easy task. The recipe has to create both graphs simultaneously, and it can't do that in any simple way, since they usually get built by completely different random processes, and they're not cooperating.

Twenty Years of Partial Progress

They proved the bottom half. Over the years, mathematicians proved the bottom half of the sandwich existed, and they proved the upper half in some settings, though it's clear they don't get there everywhere. And each step demanded serious technique. Each step demanded ingenuity too.

"It was a sequence of ideas building upon one another," said Michael Krivelevich, a mathematician at Tel Aviv University who has worked on the problem.

But the sandwich was not yet complete. A full proof would require a way to closely connect the bread and cheese of any sandwich, building the layers in tandem so they always fit together.

The Perfect Recipe

In 2023, three mathematicians started thinking about the problem. Richard Montgomery of the University of Warwick, Natalie Behague, his postdoctoral researcher at the time, and Daniel Iľkovič, his doctoral student, wanted to build a random regular graph and a random binomial graph edge by edge, ensuring at each step that the regular graph would contain the binomial one. Picture a sandwich. It's made from tiny bits of shredded cheese placed one by one, rather than slapping on a whole slice. They don't want the whole slice. And we've got to see how each shred fits.

Their recipe, heavily adapted from a 2019 result by Gao and two colleagues, works like this. Start with two sets of vertices and no edges. One set will become your binomial graph, the other your regular graph. Build the binomial graph in the usual way: choose a pair of vertices, flip a weighted coin. Heads means add an edge to the binomial graph, and add one to the regular graph as well. Tails means skip the binomial graph.

But tails does not settle the regular graph. A regular graph requires every vertex to have the same number of edges, so all required edges must be there. When the coin lands on tails, you ignore the binomial graph and flip a second weighted coin to decide whether to add an edge to the regular graph. The weight of that second coin changes as the graph grows. Behague, Iľkovič, and Montgomery found a clever way to estimate that weight as edges accumulate, guaranteeing a truly regular graph that contains the binomial one. That gives the lower half of the sandwich.

To build the upper half, they reversed the entire process. They began with two graphs containing every possible edge, then removed edges one by one until they ended up with a regular graph and a binomial graph containing it. The sandwich was finished.

"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 result, he felt "some kind of relief."

Free Sides for Everyone

The graph sandwich conjecture is resolved. So mathematicians don't have to prove every property of random regular graphs from scratch anymore, because they can now draw on the vast literature about random binomial graphs, a body of work built up over years by many researchers, and get properties automatically. Scores of results about regular graphs can now be rewritten. It's a single proof. And we've got something far leaner than before.

New results are already starting to appear. Gil Kalai of the Hebrew University of Jerusalem called the proof a meta-theorem, one that enriches the toolbox and sharpens technical teeth. Those methods might let mathematicians understand even more about network structure than they originally set out to.

They want stranger sandwiches now. Researchers hope to build more complicated ones, filled with alternating layers of binomial and regular graphs, or with other ingredients altogether, and in doing so they keep exploring how seemingly different random processes, one tightly constrained and one not, turn out to be more similar than they look. It's odd. They're not done yet. We've seen how two processes, one bound tight and one loose, can look far more alike than anyone expects. And they can't stop asking why.

"That sort of deep connection between the two," Behague said, "seems almost too good to be true."

And yet it is.