A mathematical sandwich puzzle

In 2004, mathematicians proposed a way to understand hard-to-analyze graphs by sandwiching them between two simpler graphs. Proving this sandwich exists would show the middle graph has many important properties at once.

“The notion is so beautiful.”

What graphs represent

Graphs are collections of points called vertices connected by lines called edges. They model everything from social networks to the internet to neurons in the brain.

Random binomial graphs explained

In the late nineteen fifties, Edgar Gilbert at Bell Labs created a simple random graph model. You flip a coin for each pair of vertices: heads means draw an edge, tails means skip it.

Why binomial graphs matter

Random binomial graphs are easy to analyze mathematically. By the nineteen seventies, researchers had proven many properties about them, like when they contain a Hamiltonian cycle.

Regular graphs are harder

Regular graphs require every vertex to have the same number of edges. They model real networks better than binomial graphs but are much harder to analyze because their edges form constrained, interdependent patterns.

The twenty-year gap

Mathematicians proved properties of binomial graphs by the nineteen seventies. It took another twenty years of work before they could prove the same properties for regular graphs.

Kim and Vu's sandwich idea

In the early two thousands, Jeong Han Kim and Van Ha Vu proposed building a binomial graph and regular graph simultaneously using a single recipe. This would let properties proven for the binomial graph transfer to the regular graph.

The bottom half of the sandwich

You need a recipe that creates a regular graph containing a binomial graph as a subset. Any property that appears when you add edges to the binomial graph will also appear in the regular graph.

The top half of the sandwich

You also need a recipe creating a regular graph contained within a binomial graph. Properties that appear when you remove edges from the binomial graph must also appear in the regular graph.

Decades of partial progress

Over twenty years, mathematicians proved the bottom half of the sandwich existed and the top half in some settings. But completing the full sandwich required new techniques and remained unsolved.

“It was a sequence of ideas building upon one another.”

The breakthrough in 2025

Richard Montgomery, Natalie Behague, and Daniel Iľkovič developed a method to build both graphs edge by edge simultaneously, guaranteeing they fit together perfectly at every step.

Building the sandwich layer by layer

The trio's recipe starts with two empty vertex sets. For each potential edge, flip a weighted coin. Heads adds an edge to both graphs. Tails may add an edge only to the regular graph to maintain its regularity.

The clever coin-weighting trick

As edges are added, the weight of the second coin changes dynamically. This ensures the regular graph stays truly regular while always containing the binomial graph, creating the lower sandwich layer.

Completing the sandwich

To build the upper layer, the mathematicians reversed the entire process. Starting with complete graphs, they removed edges one by one until reaching a regular graph and binomial graph that fit together.

Immediate practical benefits

Mathematicians can now rewrite scores of results about regular graphs using existing knowledge of binomial graphs. Properties proven for binomial graphs automatically apply to regular graphs without starting from scratch.

New mathematical tools emerge

The proof introduces methods that enrich mathematicians' toolkit for understanding network structure. These techniques may reveal even deeper connections between different types of random processes.

“enriches our toolbox and sharpens our technical teeth.”

Future multi-layer sandwiches

Researchers now hope to build more complex sandwiches with alternating layers of binomial and regular graphs, exploring how seemingly different random processes are fundamentally more similar than expected.

“That sort of deep connection between the two seems almost too good to be true.”