Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
Теорема Рамсея — теорема комбинаторики о разбиениях множеств, сформулированная и доказанная английским математиком Фрэнком Рамсеем в 1930 году. Встречается в литературе в разных формулировках. Эта теорема положила начало теории Рамсея.
Кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром. Клики являются одной из основных концепций теории графов и используются во многих других математических задачах и построениях с графами. Клики изучаются также в информатике — задача определения, существует ли клика данного размера в графе является NP-полной. Несмотря на эту трудность, изучаются многие алгоритмы для поиска клик.
Гипотеза Эрдёша — Бура — математическая проблема, касающаяся числа Рамсея на разреженных графах. Гипотеза названа в честь Пала Эрдёша и Стефана Бура. Гипотеза утверждает, что число Рамсея в любом семействе разреженных графов должно иметь почти линейный рост в зависимости от числа вершин графа.
В теории графов графами Пэли называются плотные неориентированные графы, построенные из членов подходящего конечного поля путём соединения пар элементов, отличающихся на квадратичный вычет. Графы Пэли образуют бесконечное семейство конференсных графов, поскольку тесно связаны с бесконечным семейством симметричных конференсных матриц. Графы Пэли дают возможность применить теоретические средства теории графов в теории квадратичных вычетов и имеют интересные свойства, что делает их полезными для теории графов в общем.
В теории графов графом без треугольников называется неориентированный граф, в котором никакие три вершины не образуют треугольник из рёбер. Графы без треугольников можно определить также как графы с кликовым числом ≤ 2, графы с обхватом ≥ 4, графы без порождённых 3-циклов, или как локально независимые графы.
В теории графов максимальным независимым множеством, максимальным устойчивым множеством, или максимальным стабильным множеством называется независимое множество, не являющееся подмножеством другого независимого множества. То есть это такое множество вершин S, что любое ребро графа имеет хотя бы одну конечную вершину, не принадлежащую S, и любая вершина не из S имеет хотя бы одну соседнюю в S. Максимальное независимое множество является также доминирующим в графе, а любое доминирующее множество, являющееся независимым, должно быть максимальным независимым, поэтому максимальные независимые множества также называют независимыми доминирующими множествами. Граф может иметь много максимальных независимых множеств в широком диапазоне размеров.
Древесность неориентированного графа — это минимальное число лесов, на которые можно разложить рёбра. Эквивалентно это является минимальным числом остовных деревьев, которые необходимы для покрытия рёбер графа.
Граф дружеских отношений Fn — это планарный неориентированный граф с 2n+1 вершинами и 3n рёбрами.
k-Вырожденный граф — это неориентированный граф, в котором каждый подграф имеет вершины со степенью, не превосходящей k. Вырожденность графа — это наименьшее значение k, для которого граф является k-вырожденным. Вырожденность графа отражает, насколько граф разрежен и отражает другие меры разреженности, такие как древесность графа.
Размерность графа — наименьшее целое n такое, что существует «классическое представление» графа в евклидовом пространстве размерности n с единичными длинами рёбер.
Неориентированный граф G называется строго хордальным, если он является хордальным и любой цикл чётной длины в G имеет нечётную хорду, то есть ребро, которое соединяет две вершины цикла на нечётном расстоянии (>1) друг от друга.
Геометрический остов или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется коэффициентом растяжения остова.
Проблема Ружи – Семереди или (6,3)-проблема спрашивает о максимальном числе рёбер в графе, в котором любое ребро принадлежит единственному треугольнику. Эквивалентно, проблема спрашивает о максимальном числе рёбер в сбалансированном двудольном графе, рёбра которого можно разбить на линейное число порождённых паросочетаний, или максимальное число троек, которые можно выбрать из 
точек так, что каждые шесть точек содержат максимум две тройки. Проблема названа именем Имре З. Ружи и Эндре Семереди, которые первыми доказали, что ответ меньше, чем 
на медленно растущий множитель.
Топологический граф — представление графа на плоскости, в котором вершины графа представлены различными точками, а рёбра кривыми Жордана, соединяющими соответствующие пары точек. Точки, представляющие вершины графа, и дуги, представляющие рёбра, называются вершинами и рёбрами топологического графа. Обычно предполагается, что любые два ребра топологического графа пересекаются конечное число раз, при этом ни одно ребро не проходит через вершину и никакие два ребра не касаются друг друга. Топологический граф называется также «рисунком» графа.
