דמיינו מדינה ובה אלף ערים, כשבין כל זוג ערים מחברת דרך ישרה. כמובן שקל לתכנן טיול שבו תעברו מעיר לעיר, תבקרו בכל עיר פעם אחת בדיוק ותחזרו לעיר שממנה יצאתם לטיול. למעשה, יש כמות עצומה של מסלולים אפשריים העונים לדרישות אלה. עתה דמיינו מצב שבו חלק מהדרכים המחברות בין זוגות ערים השתבשו בצורה אקראית; נניח שכל חיבור בין הערים שורד בסיכוי של 50%. האם גם אז אתם צפויים להיות מסוגלים לתכנן מסלול מעגלי בין כל הערים, כמו בתרחיש המקורי? כמה מהמסלולים אפשריים האלה צפויים לשרוד את השיבושים? האם עדיין יש סיכוי למצוא עשר ערים שהחיבור בין כל הזוגות שבהן לא השתבש? במונחים מתמטיים, שאלות מסוג אלה נחקרות במחקר על גרפים מקריים. זהו תחום מתמטי מופשט שהוא תת-תחום של קומבינטוריקה: המתמטיקה של בדיד. גרפים מקריים, בנוסף להיותם עצמים מופשטים, עוזרים בחקר ובמידול של הרבה תופעות טבע ורשתות. במחקר זה חקרנו תכונות של גרפים מקריים כמו גם את שרידותן של תכונות של גרפים אקראיים תחת הפרעות אקראיות.