Mathematicians Prove Graph Sandwich Conjecture After Two Decades

The Graph Sandwich Conjecture

In 2004, two mathematicians hypothesized a method to understand complex graphs by "sandwiching" them between two simpler graphs. This mathematical sandwich would allow researchers to deduce various properties of the middle graph, which is common in mathematics and computer science but difficult to analyze directly.

The conjecture stated that for a sufficiently large graph, such a sandwich could always be constructed. Proving this would not only confirm specific properties of the middle graph but also demonstrate a deeper connection between two different random processes used by mathematicians to study graphs.

Two Decades of Progress

Over the past two decades, mathematicians made incremental progress on the sandwich conjecture, but a complete proof remained elusive. The problem required pushing existing mathematical techniques to their limits.

In 2025, three mathematicians successfully found a way to complete the proof, confirming the existence of this graph sandwich for large enough graphs.

Background on Random Graphs

The concept of random graphs originated in the late 1950s with Edgar Gilbert's work on telephone networks at Bell Labs, and independently with Paul Erdős and Alfréd Rényi. These models, known as random binomial graphs, involve creating connections between vertices based on a probability.

Random binomial graphs provided a useful, though imperfect, way to represent networks and were relatively easy to analyze. Mathematicians have studied their properties, such as the conditions under which they contain a Hamiltonian cycle, since the 1970s.