In 2004, two mathematicians hypothesized a powerful kind of sandwich to understand properties of a difficult-to-analyze type of graph. They aimed to sandwich it between two simpler graphs to demonstrate its key properties and connect two random processes in a deeper way. The notion was described as "beautiful" by Pu Gao, a mathematician at the University of Waterloo in Canada.

In the late 1950s, Edgar Gilbert at Bell Labs developed random binomial graphs by flipping coins to connect vertices. Regular graphs, where all vertices have the same number of edges, are more accurate for modeling real-world networks but harder to analyze. In the early 200s, Jeong Han Kim at Microsoft Research and Van Ha Vu at UC San Diego created a graph sandwich to approximate regular graphs with binomial ones, enabling results for binomial graphs to apply to regular ones.