Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
Задача о клике относится к классу NP-полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом.
Теорема Фа́ри — теоретико-графовое утверждение о возможности выпрямить рёбра любого планарного графа. Иными словами, разрешение рисовать рёбра не в виде отрезков, а в виде кривых, не расширяет класс планарных графов.
Зада́ча о кратча́йшем пути́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.
В теории графов нечётные графы On — это семейство симметричных графов с высоким нечётным обхватом, определённых на некоторых семействах множеств. Они включают и обобщают графы Петерсена.
В теории графов графом без треугольников называется неориентированный граф, в котором никакие три вершины не образуют треугольник из рёбер. Графы без треугольников можно определить также как графы с кликовым числом ≤ 2, графы с обхватом ≥ 4, графы без порождённых 3-циклов, или как локально независимые графы.
Задача о трёх домиках и трёх колодцах — классическая математическая головоломка: проложить от каждого из трёх колодцев к каждому из трёх домиков непересекающиеся тропинки. Формулировка задачи приписывается Эйлеру. В современной литературе иногда встречается в следующей форме: возможно ли к каждому из трёх домиков проложить без пересечений на плоскости трубы (рукава) от трёх источников — электроснабжения, газоснабжения и водоснабжения.
В теории графов ладе́йным гра́фом называется граф, представляющий все допустимые ходы ладьи на шахматной доске — каждая вершина представляет клетку на доске, а рёбра представляют возможные ходы. Ладейные графы являются крайне симметричными совершенными графами — их можно описать в терминах числа треугольников, которым принадлежит ребро и существования цикла длины 4, включающего любые две несмежные вершины.
В теории графов графом ходов коня называется граф, изображающий все возможные ходы коня на шахматной доске — каждая вершина соответствует клетке на доске, а рёбра соответствуют возможным ходам.
Базис циклов неориентированного графа — множество простых циклов, которые образуют базис пространства циклов графа. Таким образом, это минимальный набор циклов, который позволяет любой эйлеров подграф представить как симметрическую разность базисных циклов.
Замощение плитками домино области в евклидовой плоскости — мозаика из плиток домино, которые образованы объединением двух единичных квадратов, соединённых по ребру. Эквивалентно — это паросочетание в графе решётки, образованное помещением вершины в центр каждого квадрата области и соединением двух вершин, если два соответствующих квадрата смежны.
1-планарный граф — граф, который может быть нарисован в евклидовой плоскости таким образом, что каждое ребро имеет максимум одно пересечение с единственным другим ребром. Естественное обобщение — 
-планарный граф.
Ребро в геометрии — отрезок, соединяющий две вершины многоугольника или многогранника. В многоугольниках ребро является отрезком, лежащим на границе и чаще называется стороной многоугольника. В трёхмерных многогранниках и в многогранниках большей размерности ребро — это отрезок, общий для двух граней. Отрезок, соединяющий две вершины и проходящий через внутренние или внешние точки, ребром не является и называется диагональю.
FKT — алгоритм, подсчитывающий число совершенных паросочетаний в планарном графе за полиномиальное время. Та же задача является #P-полной для общих графов. Вычисление числа паросочетаний даже для планарных графов является также #P-полной задачей. Ключевой идеей является сведение задачи к вычислению пфаффиана кососимметричной матрицы, полученной из планарного вложения графа. Пфаффиан этой матрицы вычисляется тогда эффективно с помощью стандартных алгоритмов вычисления определителя.
Граф вложенных треугольников с n вершинами — это планарный граф, образованный последовательностью n/3 треугольников, соответствующие пары вершин которых соединяются рёбрами. Он может быть образован также геометрически путём склеивания вместе 
треугольных призм по их треугольным граням. Этот граф и тесно связанные графы часто используются в области визуализации графов для доказательства нижних границ требующейся площади при различных стилях рисования.
Граф судоку — это неориентированный граф, вершины которого представляют ячейки (пустой) головоломки судоку, а рёбра представляют пары ячеек, которые принадлежат той же строке, тому же столбцу или блоку головоломки. Задача головоломки судоку может быть представлена как расширение предварительной раскраски на этом графе. Граф является целочисленным графом Кэли.
