Теорія графів розділ дискретної математики, що вивчає графи. У найзагальнішому сенсі граф – це безліч точок (вершин, вузлів), які з'єднуються безліччю ліній (ребер, дуг).
Граф — це геометрична фігура, яка складається з точок та ліній, що їх з'єднують. Крапки називають вершинами графа, А лінії – ребрами. Два ребра називаються суміжними, якщо вони мають загальна вершина. Два ребра називаються кратними, якщо вони з'єднують ту саму пару вершин.
Для знаходження найкоротшого чи об'їзного шляху, раціонального маршруту пересування, для оптимізації виробничого циклу застосовується теорія графів. В економічній сфері завдання теорії графів застосовуються для прийняття локально оптимальних рішень кожному етапі, причому кінцеве рішення також виявиться оптимальним.
Теорема 1. Сума ступенів усіх вершин графа дорівнює подвоєній кількості ребер.