Mathematicians Build Long-Awaited Graph Sandwich

Recorded: Sept. 18, 2026, 4:09 p.m.

Original

Summarized

Mathematicians Build Long-Awaited Graph Sandwich | Quanta Magazine

Quanta Homepage

Physics

Mathematics

Biology

Computer Science

Topics

Popular
Searches

Mathematics

Physics

Black Holes

Evolution

Home

Mathematicians Build Long-Awaited Graph Sandwich

Comment

Save Article

Read Later

Facebook

Copied!

Copy link

Pocket

Ycombinator

Comment

Comments

Save Article
Read Later

Read Later

graph theory
Mathematicians Build Long-Awaited Graph Sandwich

Paulina Rowińska

September 18, 2026

The proof of a decades-old conjecture has given researchers a new way to understand complex networks.

Comment

Save Article

Read Later

Kristina Armitage/Quanta Magazine

Introduction

By Paulina Rowińska
Contributing Writer

September 18, 2026

View PDF/Print Mode

combinatorics

graph theory

mathematics

probability

randomness

All topics

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.

Share this article

Facebook

Copied!

Copy link

Pocket

Ycombinator

Newsletter

Get Quanta Magazine delivered to your inbox

Subscribe now

Mark Belan/Quanta Magazine

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.
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, 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 Perfect Recipe
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 of the University of Warwick; Natalie Behague, his postdoctoral researcher at the time; and Daniel Iľkovič, 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.

Lisa Sauermann

To follow their recipe (which, the mathematicians note, is heavily adapted from a 2019 result 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.”
Free Sides
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.

‘Stunning’ Percolation Proof Solves Decades-Old Puzzle About Phase Transitions

Elegant Six-Page Proof Reveals the Emergence of Random Structure

New Proof Settles Decades-Old Bet About Connected Networks

That means they can rewrite scores of results about regular graphs in a single, streamlined proof. And new results are already starting to appear.
Moreover, the proof of this “meta-theorem,” as Gil Kalai 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.

By Paulina Rowińska
Contributing Writer

September 18, 2026

View PDF/Print Mode

combinatorics

graph theory

mathematics

probability

randomness

All topics

Share this article

Facebook

Copied!

Copy link

Pocket

Ycombinator

Newsletter

Get Quanta Magazine delivered to your inbox

Subscribe now

The Quanta Newsletter

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

Also in Mathematics

The Four-Color Theorem Gets a Rare New Proof

graph theory

The Four-Color Theorem Gets a Rare New Proof

Gregory Barber

September 10, 2026

Comment

Save Article

Read Later

What Is Math’s Mysterious Langlands Program Really About?

Qualia

What Is Math’s Mysterious Langlands Program Really About?

Natalie Wolchover

September 9, 2026

Comment

Save Article

Read Later

AI Has Solved One of Math’s $1 Million Millennium Prize Problems

artificial intelligence

AI Has Solved One of Math’s $1 Million Millennium Prize Problems

Konstantin Kakaes

September 8, 2026

Comment

Save Article

Read Later

Comment on this article

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.

Show comments

Next article
Where Does the Quantum World End and Ours Begin?

Quanta Homepage

Facebook

Youtube

Instagram

Newsletter

About Quanta

Archive

Terms & Conditions

AI Editorial Policy

An editorially independent publication supported by the Simons Foundation.

Simons Foundation

Use your social network

Facebook Connect with Facebook

Connect with Google

password

Remember me

Forgot your password ?

Don't have an account yet?
Sign up

Forgot your password?
We’ll email you instructions to reset your password

Change your password
Enter your new password

Password

Retype new password

First Name

Last Name

Password

Retype Password

Creating an account means you accept Quanta Magazine's

Terms & Conditions and Privacy Policy

Mathematicians have made significant progress in resolving a long-standing conjecture regarding the relationship between different types of graphs, which provides a new method for understanding complex networks. The underlying idea involves creating a mathematical "sandwich" by rigorously placing a graph of interest between two simpler graphs, aiming to demonstrate that the middle graph inherits all the important properties of both bounding graphs. This endeavor aims to show an elegant connection between two disparate random processes frequently studied in mathematics.

This research stems from the distinction between random binomial graphs and random regular graphs. Binomial graphs, introduced by models like those of Erdős and Rényi, originate from a process where edges are chosen randomly between pairs of vertices, while regular graphs are those where all vertices possess the same number of edges, and they are often more accurate for modeling real-world networks despite being harder to analyze due to their constrained, interdependent patterns. The challenge has been to find a unified random process that could generate both types of graphs simultaneously while ensuring they fit together cohesively.

Jeong Han Kim and Van Ha Vu initially proposed an approach by seeking a single recipe for generating both a binomial graph and a regular graph. This recipe needed to produce graphs that related in a specific way, establishing the lower layer of the sandwich where the binomial graph's edges formed a subset of the regular graph's edges. Furthermore, they needed a relationship where the regular graph was contained within the binomial graph, establishing the upper layer.

The complete conjecture required establishing a method to ensure these layers fit together seamlessly. The breakthrough involved rethinking the construction process by building the graphs edge by edge in tandem. Richard Montgomery, Natalie Behague, and Daniel Iľkovič developed a specific recipe where edges were added incrementally, ensuring that at each step the resulting structure maintained the required relationship. For the lower half of the sandwich, they employed a weighted coin process to select edges, and a separate technique was used to guarantee the resulting structure was regular while containing the binomial graph. For the upper half, they reversed the process, starting from graphs containing all possible edges and removing them sequentially until the desired properties were achieved.

This intricate method allowed the mathematicians to prove the conjecture. The resolution means that researchers no longer need to prove every property of random regular graphs from scratch; they can instead utilize the extensive literature on random binomial graphs to automatically deduce properties of regular graphs. This result provides a streamlined proof, enriching the mathematical toolbox and sharpening methods for understanding network structures. Consequently, researchers are now exploring even more complex sandwiches, alternating layers of binomial and regular graphs, to further explore the deep similarities between seemingly different random processes.