Mathematicians have resolved a conjecture that remained unproven for more than two decades, establishing a powerful connection between two types of random graphs. The breakthrough could simplify research into complex networks, including communication systems, social connections, and neural networks, says Quanta Magazine.
The graph sandwich conjecture, proposed in 2004 by Jeong Han Kim and Van Ha Vu, concerns random regular graphs, in which every vertex has the same number of connections. Although these graphs can model real-world networks, their interdependent connections make them difficult to analyze mathematically.
By contrast, random binomial graphs are easier to study because connections between vertices are generated independently using fixed probabilities.
Kim and Vu proposed placing a random regular graph between two binomial graphs, with the smaller graph contained within the regular graph and the regular graph contained within the larger one. This arrangement would allow researchers to transfer established mathematical properties from simpler graphs to more complicated structures.
In 2025, Richard Montgomery, Natalie Behague, and Daniel Iľkovič completed the proof using an innovative construction method.
Their approach builds binomial and regular graphs simultaneously, adding edges one at a time. A weighted coin determines whether an edge appears in both graphs. A second coin, whose probability changes throughout construction, determines whether additional edges are needed to maintain the regular graph’s structure.
The researchers then reversed the process, starting with complete graphs and removing edges to construct the upper portion of the sandwich.
The result establishes a rigorous relationship between two previously difficult-to-reconcile random processes.
For mathematicians, the breakthrough eliminates the need to establish numerous properties of random regular graphs independently. Existing results for binomial graphs can now support broader conclusions, potentially replacing lengthy proofs with streamlined arguments.
The researchers also envision more elaborate graph sandwiches that could reveal deeper relationships between mathematical models and provide new methods for investigating complex networks.
