2004年、2人の数学者が、分析が難しいタイプのグラフの性質を理解するために、強力な種類のサンドイッチ構造を仮定しました。彼らはそれを2つのより単純なグラフの間に挟み込むことで、その主要な性質を示し、2つのランダム過程をより深いレベルで結びつけることを目指しました。この概念は、カナダのウォータールー大学の数学者Pu Gaoによって「美しい」と表現されました。1950年代後半、ベル研究所のEdgar Gilbertがコインを投げて頂点を接続することでランダム二項グラフを開発しました。すべての頂点が同じ数の辺を持つ正則グラフは、現実世界のネットワークをモデル化するのにより正確ですが、分析がより困難です。2000年代初頭、Microsoft ResearchのJeong Han KimとUC San DiegoのVan Ha Vuが、二項グラフで正則グラフを近似するグラフ・サンドイッチを作成し、二項グラフの結果を正則グラフに適用可能にしました。