Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
В теории графов теорема Кёнига , доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах. Независимо была открыта, в том же 1931, Йенё Эгервари в несколько более общем виде для случая взвешенных графов.
Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром.
Гамильтонов граф — граф, содержащий гамильтонов цикл. При этом гамильтоновым циклом является такой цикл, который проходит через каждую вершину данного графа ровно по одному разу; то есть простой цикл, в который входят все вершины графа.
В теории графов два типа объектов обычно называются циклами.
В теории графов паросочетание, или независимое множество рёбер в графе, — это набор попарно несмежных рёбер.
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.
Мост — ребро в теории графов, удаление которого увеличивает число компонент связности. Такие рёбра также известны как разрезающие рёбра, разрезающие дуги или перешейки. Эквивалентное определение — ребро является мостом в том и только в том случае, если оно не содержится ни в одном цикле.
В теории графов говорят, что нетривиальный граф G вершинно k-связен, если он имеет больше чем k вершин и после удаления менее чем k любых вершин граф остаётся связным.
Рёберно k-связный граф — граф, который остаётся связным после удаления не более чем 
рёбер.
В теории графов графом пересечений называется граф, представляющий схему пересечений семейства множеств. Любой граф можно представить как граф пересечений, но некоторые важные специальные классы можно определить посредством типов множеств, используемых для представления в виде пересечений множеств.
Нигде не нулевой поток в теории графов — специальный вид сетевого потока, который связан (двойственностью) с раскраской планарных графов.
Теорема Оре — результат в теории графов, доказанный в 1960 году норвежским математиком Ойстином Оре. Теорема даёт достаточное условие для того, чтобы граф был гамильтоновым, по существу утверждая, что граф с «достаточно большим числом рёбер» должен содержать гамильтонов цикл. В частности, теорема рассматривает суммы степеней пар несмежных вершин — если каждая такая пара в сумме даёт как минимум общее число вершин графа, граф является гамильтоновым.
Сильная ориентация неориентированного графа — это назначение направлений каждому ребру, при котором граф превращается в сильно связный граф.
Теорема Роббинса, названная по имени американского математика Герберта Роббинса, утверждает, что графы, имеющие сильные ориентации, — это в точности рёберно 2-связные графы. То есть тогда и только тогда можно выбрать направление каждого ребра неориентированного графа G, превратив граф в ориентированный граф, в котором существует (ориентированный) путь из любой вершины в любую другу вершину, когда граф G связен и не имеет мостов.
Теорема Гринберга — необходимое условие для планарного графа, чтобы он содержал гамильтонов цикл, основанное на длинах циклов граней. Результат широко используется для построения негамильтоновых графов с дополнительными свойствами. Например, были построены новые контрпримеры гипотезе Тэйта. Теорему доказал латвийский математик Эмануэль Гринберг в 1968 году.
Наименьший разрез графа — это минимальный в некотором смысле разрез.
Пространство циклов неориентированного графа — линейное пространство над полем 
, состоящее из его эйлеровых подграфов. Размерность этого пространства называется контурным рангом графа. С точки зрения алгебраической топологии циклическое пространство является первой группой гомологий графа.
