Em 2004, dois matemáticos hipotetizaram um tipo poderoso de sanduíche para entender as propriedades de um tipo de grafo difícil de analisar. Eles pretendiam colocá-lo entre dois grafos mais simples para demonstrar suas propriedades-chave e conectar dois processos aleatórios de forma mais profunda. A noção foi descrita como "bonita" por Pu Gao, matemático da Universidade de Waterloo no Canadá.

No final dos anos 1950, Edgar Gilbert nos Bell Labs desenvolveu grafos binomiais aleatórios lançando moedas para conectar vértices. Grafos regulares, onde todos os vértices têm o mesmo número de arestas, são mais precisos para modelar redes do mundo real, mas mais difíceis de analisar. No início dos anos 2000, Jeong Han Kim na Microsoft Research e Van Ha Vu na UC San Diego criaram um sanduíche de grafos para aproximar grafos regulares com binomiais, permitindo que resultados para grafos binomiais se aplicassem aos regulares.