Граф — математическая абстракция реальной системы любой природы, объекты которой обладают парными связями. Граф как математический объект есть совокупность двух множеств — множества самих объектов, называемого множеством вершин, и множества их парных связей, называемого множеством рёбер. Элемент множества рёбер есть пара элементов множества вершин.

Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.

В теории графов теорема Кёнига , доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах. Независимо была открыта, в том же 1931, Йенё Эгервари в несколько более общем виде для случая взвешенных графов.

Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
Зада́ча о незави́симом мно́жестве относится к классу NP-полных задач в области теории графов. Эквивалентна задаче о клике.
В теории графов паросочетание, или независимое множество рёбер в графе, — это набор попарно несмежных рёбер.
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.

В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).

В теории графов циркулянтным графом называется неориентированный граф, имеющий циклическую группу симметрий, которая включает симметрию, переводящую любую вершину в любую другую вершину.

В теории графов граф перестановки — это граф, вершины которого соответствуют элементам перестановки, а рёбра представляют пары элементов, следование которых стало обратным после перестановки. Графы перестановки можно определить геометрически как графы пересечений отрезков, концы которых лежат на двух параллельных прямых. Различные перестановки могут дать один и тот же граф перестановки. Заданный граф имеет единственное представление если он является простым с точки зрения модульной декомпозиции.

В теории графов кограф, или дополнительно сводимый граф, или граф, свободный от P4, — это граф, который можно получить из графа с единственной вершиной K1 путём операций дополнения и объединения графов. Таким образом, семейство кографов — это наименьший класс графов, содержащий K1 и замкнутый относительно дополнения и объединения.

В теории графов полная раскраска — это противоположность гармонической раскраске в том смысле, что это раскраска вершин, в которой каждая пара цветов встречается по меньшей мере на одной паре смежных вершин. Эквивалентно, полная раскраска — это минимальная раскраска, в том смысле, что её нельзя преобразовать в правильную раскраску с меньшим числом цветов путём слияния двух цветов. Ахроматическое число ψ(G) графа G — это максимальное число цветов среди всех полных раскрасок графа G.

k-дольный граф — граф, множество вершин которого можно разбить на k независимых множеств (долей). Эквивалентно, это граф, который можно раскрасить с помощью k цветов так, что концы любого выбранного ребра будут окрашены в разные цвета. При k = 2 k-дольный граф называется двудольным.

Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные.
Модульное разложение — это разложение графа на подмножества вершин, называемых модулями. Модуль является обобщением компоненты связности графа. В отличие от компонент связности, однако, один модуль может быть собственным подмножеством другого. Модули, поэтому, ведут к рекурсивной (иерархической) декомпозиции графа, а не просто к разбиениям.
Предписанная раскраска — это вид раскраски графов, в которой каждая вершина может принимать ограниченное множество допустимых цветов. Одними из первых эту раскраску изучили Визинг и Эрдёш, а также Рубин и Тейлор в 1970-х годах.
Пространство циклов неориентированного графа — линейное пространство над полем
, состоящее из его эйлеровых подграфов. Размерность этого пространства называется контурным рангом графа. С точки зрения алгебраической топологии циклическое пространство является первой группой гомологий графа.