2004 में, दो गणितज्ञों ने एक शक्तिशाली प्रकार के सैंडविच की परिकल्पना की ताकि एक कठिन-से-विश्लेषण ग्राफ प्रकार के गुणों को समझा जा सके। उनका उद्देश्य इसे दो सरल ग्राफ के बीच सैंडविच करना था ताकि इसके प्रमुख गुणों को प्रदर्शित किया जा सके और दो यादृच्छिक प्रक्रियाओं को गहरे तरीके से जोड़ा जा सके। इस धारणा को कनाडा में वाटरलू विश्वविद्यालय के गणितज्ञ पु गाओ (Pu Gao) द्वारा "सुंदर" बताया गया था। 1950 के दशक के अंत में, बेल लैब्स के एडगर गिल्बर्ट (Edgar Gilbert) ने सिक्के उछालकर शीर्षों को जोड़कर यादृच्छिक द्विपद ग्राफ विकसित किए। नियमित ग्राफ, जहां सभी शीर्षों में समान संख्या में किनारे होते हैं, वास्तविक दुनिया के नेटवर्क को मॉडल करने के लिए अधिक सटीक हैं लेकिन विश्लेषण करना कठिन है। 2000 के दशक की शुरुआत में, माइक्रोसॉफ्ट रिसर्च के जियोंग हान किम (Jeong Han Kim) और यूसी सैन डिएगो के वान हा वू (Van Ha Vu) ने नियमित ग्राफ को द्विपद ग्राफ से अनुमानित करने के लिए एक ग्राफ सैंडविच बनाया, जिससे द्विपद ग्राफ के परिणाम नियमित ग्राफ पर लागू हो सके।