В основе теории графов лежат следующие математические структуры:

1. Граф. 15 Это математическая структура, состоящая из двух множеств: множества вершин и множества рёбер. 1 Вершины представляют объекты или сущности, а рёбра — связи или отношения между парами вершин. 1
2. Вершина. 1 Базовый элемент графа, обозначающий объект или сущность в рассматриваемой системе. 1
3. Ребро. 1 Соединение между двумя вершинами, отражающее существование связи или отношения между ними. 1
4. Инцидентность и смежность. 1 Эти понятия описывают отношения между вершинами и рёбрами в графе. 1

Также в основе теории графов лежат такие понятия, как ориентированный граф (в котором каждое ребро указывает своё направление) и неориентированный граф (в котором рёбра не указывают направление). 2