Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
Матрица смежности — один из способов представления графа в виде матрицы.
В теории графов циркулянтным графом называется неориентированный граф, имеющий циклическую группу симметрий, которая включает симметрию, переводящую любую вершину в любую другую вершину.
В теории графов графом пересечений называется граф, представляющий схему пересечений семейства множеств. Любой граф можно представить как граф пересечений, но некоторые важные специальные классы можно определить посредством типов множеств, используемых для представления в виде пересечений множеств.
Дистанционно-транзитивный граф — граф, в котором любая упорядоченная пара вершин переводится в любую другую упорядоченную пару вершин с тем же расстоянием между вершинами одним из автоморфизмов графа.
Вершинa графа — фундаментальное понятие теории графов. Неориентированный граф состоит из множества вершин и множества рёбер, в то время как ориентированный граф состоит из множества вершин и множества дуг. На рисунках, представляющих граф, вершина обычно обозначается кружком с меткой, ребро — линией, дуга — стрелкой, соединяющей вершины.
Спектральная теория графов — направление в теории графов, изучающее свойства графов, характеристических многочленов, собственных векторов и собственных значений матриц, связанных с графом, таких, как его матрица смежности или матрица Кирхгофа.
В математике два-граф это (неупорядоченное) множество троек, выбранных из конечного множества вершин X таким образом, что любая (неупорядоченная) четвёрка из X содержит чётное число выбранных троек два-графа. В регулярном (однородном) два-графе любая пара вершин лежит в одном и том же числе троек два-графа. Два-графы изучаются ввиду их связи с равноугольными прямыми, связи регулярных два-графов с сильно регулярными графами, а также ввиду связи регулярных два-графов с конечными группами, поскольку многие из этих графов имеют интересные группы автоморфизмов.
Древесность неориентированного графа — это минимальное число лесов, на которые можно разложить рёбра. Эквивалентно это является минимальным числом остовных деревьев, которые необходимы для покрытия рёбер графа.
В теории графов контурный ранг неориентированного графа — это минимальное число рёбер, удаление которых разрушает все циклы графа, превращая его в дерево или лес. Контурный ранг можно понимать также как число независимых циклов в графе. В отличие от соответствующей задачи нахождения разрезающего циклы набора дуг для ориентированных графов, контурный ранг r легко вычисляется по формуле
,
В теории графов псевдолес — это неориентированный граф, в котором любая связная компонента имеет максимум один цикл. То есть это система вершин и рёбер, соединяющих пары вершин, такая, что никакие два цикла не имеют общих вершин и не могут быть связаны путём. Псевдодерево — это связный псевдолес.
Циклический ранг ориентированного графа — мера связности орграфа, предложенная Эгганом и Бучи. Это понятие интуитивно отражает, насколько близок орграф к направленному ациклическому графу, когда циклический ранг НАГ равен нулю, в то время как ориентированный орграф порядка n с петлями в каждой вершине имеет циклический ранг n. Циклический ранг ориентированного графа тесно связан с глубиной дерева неориентированного графа и высотой итерации регулярных языков. Циклический ранг нашёл применение также в вычислениях с разреженными матрицами и логике.
Книга может быть любым графом некоторого вида, который образован циклами, имеющими общее ребро.
Целый граф — граф, спектр матрицы смежности которого состоит полностью из целых чисел. Другими словами, граф является целым графом, при условии, что все корни характеристического многочлена его матрицы смежности являются целыми числами. Понятие ввели в 1974 году Харари и Швенк.
Граф Берлекэмпа — ван Линта — Зейделя — это локально линейный сильно регулярный граф с параметрами (243,22,1,2), это означает, что граф имеет 243 вершины, 22 ребра на вершину, в точности одну общую вершину для каждой пары смежных вершин и в точности две общие вершины для любой пары несмежных. Граф построили Элвин Берлекэмп, Дж. Г. ван Линт и Йохан Якоб Зайдель как граф смежности троичных кодов Голея.
Пространство столбцов матрицы 
— это линейная оболочка её вектор-столбцов. Пространство столбцов матрицы также является образом или областью значений соответствующего ей отображения.
Пространство циклов неориентированного графа — линейное пространство над полем 
, состоящее из его эйлеровых подграфов. Размерность этого пространства называется контурным рангом графа. С точки зрения алгебраической топологии циклическое пространство является первой группой гомологий графа.
