En 2004, dos matemáticos hipotetizaron un poderoso tipo de sándwich para entender las propiedades de un tipo de grafo difícil de analizar. Su objetivo era colocarlo entre dos grafos más simples para demostrar sus propiedades clave y conectar dos procesos aleatorios de una manera más profunda. La noción fue descrita como "hermosa" por Pu Gao, matemático de la Universidad de Waterloo en Canadá.

A finales de la década de 1950, Edgar Gilbert en Bell Labs desarrolló grafos binomiales aleatorios lanzando monedas para conectar vértices. Los grafos regulares, donde todos los vértices tienen el mismo número de aristas, son más precisos para modelar redes del mundo real pero más difíciles de analizar. A principios de la década de 2000, Jeong Han Kim en Microsoft Research y Van Ha Vu en UC San Diego crearon un sándwich de grafos para aproximar grafos regulares con binomiales, permitiendo que los resultados para grafos binomiales se aplicaran a los regulares.