In 2004, two mathematicians came up with a plan for a sandwich that was not made of bread and cheese. It was made of graphs. They wanted to understand one kind of graph — one that shows up everywhere in math and computer science but is hard to study — by putting it between two simpler graphs. If the sandwich worked, the middle graph would inherit all sorts of useful qualities from the outer ones. The idea was simple. The execution took twenty years.
What Is a Graph?
A graph is a collection of points, called vertices, joined by lines, called edges. Those edges can stand for almost anything: friendships, web pages linked together, neurons firing in the brain. Mathematicians have spent generations studying how these connections behave, and one particular kind of graph — the regular graph — has always been a troublemaker. Its edges form tight, interdependent patterns that resist easy analysis.
Random Binomial Graphs
The easier kind of graph comes from a model developed in the late 1950s by Edgar Gilbert at Bell Labs. He was looking at telephone networks, and he invented a simple way to build a “random” graph. Start with a set of vertices. Pick any pair of them. Flip a coin. Heads means you draw an edge between them; tails means you move on. Repeat until every pair has been considered.
This model became known as the random binomial graph. It was relatively easy to analyze, and by the 1970s, mathematicians had figured out exactly when one of these graphs would contain a Hamiltonian cycle — a path that touches every vertex exactly once. That was an interesting discovery.
Regular Graphs Are Harder
Then came the regular graphs. These are graphs where every vertex has the same number of edges. They are often more accurate at modeling real-world networks than binomial graphs, but they are much harder to study. It took 20 years beyond the Hamiltonian cycle result for binomial graphs before anyone could prove the same thing for regular graphs.
The difficulty comes from the interdependence of the edges. In a regular graph, adding or removing an edge in one place affects the graph’s structure elsewhere. That makes them a pain to work with.
Kim and Vu’s Idea
Jeong Han Kim, then at Microsoft Research, and Van Ha Vu, then at the University of California, San Diego, had a plan. They wanted to approximate regular graphs with binomial graphs. If that were possible, the hard-to-prove qualities of a regular graph could come along for free, inherited from the simpler graph. Their idea was to build a sandwich — a binomial graph on the bottom, a regular graph in the middle, and another binomial graph on top — and show that the middle graph had to match the outer ones in certain ways.
The analogy is literal: the binomial graphs are the bread, the regular graph is the cheese, and the recipe has to layer them so that the cheese always fits between the slices. That is the whole point. Prove something about the bread, and you know the cheese is carrying the same property.
How the Layers Hold Together
The sandwich has two halves. The bottom half asks for a recipe that gives you a regular graph containing a binomial graph. The binomial graph’s edges are a subset of the regular graph’s edges. If the binomial graph gains a quality by adding edges, the regular graph inherits it. The top half asks for a recipe that gives you a regular graph contained within a binomial graph. If the binomial graph loses a quality by removing edges, the regular graph loses it too.
Kim and Vu conjectured that so long as the regular graph has a reasonable number of edges, you can almost always build this sandwich. That is a bold claim. The challenge is that the two outer graphs usually get built using completely different random processes, and the recipe has to work for both at once.
The Proof Arrives
Over the years, mathematicians proved the bottom half of Kim and Vu’s sandwich. They also proved the upper half in some settings. But the sandwich was not complete. The full proof required a way to connect the bread and cheese of any sandwich, building the layers in tandem so they always fit together.
In 2025, three mathematicians found a way to push their field’s techniques to their limits, and completed the quest. The proof of the conjecture was complete.
Why the Sandwich Matters
The significance is not just theoretical. The sandwich connects two very different random processes that mathematicians study. It shows that those processes are connected in a deeper and more elegant way than anyone had imagined. The result is a bridge between two worlds of graph theory, and it opens doors for further research.
Pu Gao, a mathematician at the University of Waterloo who has worked on the problem, put it plainly: “The notion is so beautiful.” She added, “What attracts me most is actually the beauty of it.”
Michael Krivelevich, a mathematician at Tel Aviv University who has also worked on the problem, described the progress as a sequence of ideas building upon one another. Each step, he said, “requires a very good technique. It requires ingenuity.”
The Long Road to Completion
The road from conjecture to proof was long. Here is the rough shape of it:
- 2004: Kim and Vu formulate the sandwich conjecture.
- Late 1950s: Gilbert invents the random binomial graph model; Erdős and Rényi develop a similar model independently.
- 1970s: Mathematicians prove when binomial graphs contain Hamiltonian cycles.
- After the 1970s: Mathematicians solve the equivalent problem for regular graphs, 20 years after the binomial result.
- 2025: Three mathematicians complete the proof of the sandwich conjecture.
The key facts are simple to state:
- Conjecture formulated: 2004
- Binomial graph model: late 1950s (Gilbert); similar model by Erdős and Rényi
- Hamiltonian cycle proven for binomial graphs: 1970s
- Hamiltonian cycle proven for regular graphs: 20 years after the binomial result
- Proof completed: 2025
What Comes Next
The sandwich is now a tool. It will likely be used to prove new properties of regular graphs, and it may lead to new connections between different models of random networks. The beauty of the idea, as Gao noted, is that it brings two very different worlds into alignment.
The proof is a milestone. It demonstrates that two random processes are connected in a deeper way than expected, and it opens a door to what comes next. For mathematicians, the sandwich is a reminder that sometimes the best way to understand something is to put it between two things you already know.
The journey from 2004 to 2025 involved decades of incremental progress, each step building on the last. The final breakthrough came from three mathematicians who pushed existing techniques to their limits. The result is a bridge between two worlds of graph theory, and it opens doors for further research.
Source material: “Mathematicians Build Long-Awaited Graph Sandwich,” Quanta Magazine.
Get the Notebook.
The day's best stories and every fresh verdict, in plain English, in your inbox by seven. One email a day, no more.