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.

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