Mathematicians Prove the Kim–Vu Graph Sandwich Conjecture After Two Decades

Three mathematicians have proven the full Kim–Vu sandwich conjecture in graph theory, showing that any large enough random regular graph can be 'sandwiched' between two random binomial graphs built from the same process. The result connects two major families of random graphs and lets researchers transfer decades of results from the well-understood binomial case to the harder regular case in a single meta-proof.

Key Takeaways

Three mathematicians have proven the full Kim–Vu sandwich conjecture in graph theory, showing that any large enough random regular graph can be 'sandwiched' between two random binomial graphs built from the same process.
The result connects two major families of random graphs and lets researchers transfer decades of results from the well-understood binomial case to the harder regular case in a single meta-proof.

AI synthesis1 source1

In 2004, mathematicians Jeong Han Kim and Van Ha Vu conjectured that any sufficiently large random regular graph — a graph where every vertex has the same number of edges — could be 'sandwiched' between two random binomial graphs built from the same random process. If true, this would mean that properties proved about the easier binomial graphs automatically hold for the harder regular graphs, effectively transferring decades of mathematical results in one sweep.

The conjecture has now been proven in full by Richard Montgomery of the University of Warwick, along with Natalie Behague and Daniel Iľkovič. Their proof constructs the sandwich by building both graphs edge by edge in tandem, using a carefully weighted two-coin procedure: one coin decides whether to add an edge to the binomial graph, and a second, dynamically weighted coin handles the regular graph's constraint that every vertex must end up with the same degree.

The lower half of the sandwich — showing that a regular graph can always contain a binomial subgraph — had been established earlier. The upper half, showing a regular graph can always be contained within a larger binomial graph, was the missing piece that the new proof resolves by reversing the entire construction process.

The result is what mathematician Gil Kalai of the Hebrew University of Jerusalem called a 'meta-theorem': any property that holds with high probability for random binomial graphs now automatically holds for random regular graphs, provided the graph is large enough. This means scores of previously separate results can now be unified under a single framework.

Random regular graphs are widely used to model real-world networks — from social connections to the internet to neural pathways — because their uniform edge structure captures constraints that binomial models miss. The sandwich proof opens the door to applying the vast existing literature on binomial graphs to these more realistic models, and the new proof techniques themselves may enable further results about network structure.

The mathematicians say they hope to extend the sandwich idea to even more complex layered constructions in future work.