نظریه گراف شاخه ای از ریاضیات است که درباره اشیاء خاصی در ریاضی به نام گراف بحث می‌کند. به صورت شهودی گراف نمودار یا دیاگرامی است شامل تعدادی رأس که با یالهایی به هم وصل شده‌اند. تعریف دقیق‌تر گراف به این صورت است که گراف مجموعه‌ای از رأس‌ها است که توسط خانواده‌ای از زوج‌های مرتب که همان یال‌ها هستند به هم مربوط شده‌اند.