Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.
Теорема Фа́ри — теоретико-графовое утверждение о возможности выпрямить рёбра любого планарного графа. Иными словами, разрешение рисовать рёбра не в виде отрезков, а в виде кривых, не расширяет класс планарных графов.
Граф Грёча — граф без треугольников с 11 вершинами, 20 рёбрами, хроматическим числом 4 и числом скрещиваний 5. Граф назван в честь немецкого математика Герберта Грёча и он демонстрирует необходимость предположения планарности в теореме Грёча, которая утверждает, что любой планарный граф без треугольников можно раскрасить в 3 цвета. Граф Грёча является членом бесконечной последовательности графов без треугольников, в которой каждый граф является мычельскианом предыдущего графа, начиная с нуль-графа. Эта последовательность графов была использована Мыцельским, чтобы показать, что существуют графы без треугольников с произвольно большим хроматическим числом. По этой причине иногда граф Грёча называют графом Мыцельского или Мыцельского-Грёча. В отличие от других, более поздних графов в последовательности, граф Грёча является наименьшим графом без треугольников с его хроматическим числом.
В теории графов графом без треугольников называется неориентированный граф, в котором никакие три вершины не образуют треугольник из рёбер. Графы без треугольников можно определить также как графы с кликовым числом ≤ 2, графы с обхватом ≥ 4, графы без порождённых 3-циклов, или как локально независимые графы.
В теории графов колесом Wn называется граф с n вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами (n-1)-цикла. Числовое обозначение колёс в литературе не устоялось — некоторые авторы используют n для обозначения длины цикла, так что их Wn означает граф Wn+1 по определению выше. Колесо может быть определено также, как 1-скелет (n-1)-угольной пирамиды.
Куби́ческий граф — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным. Кубические графы называются также тривалентными.
Двойное покрытие циклами в теории графов — множество циклов в неориентированном графе, которое включает в себя каждое ребро ровно два раза. Например, любой полиэдральный граф образован из вершин и рёбер выпуклого многогранника, грани же при этом образуют двойное покрытие циклами: каждое ребро принадлежит ровно двум граням.
Панциклический граф — ориентированный или неориентированный граф, который содержит циклы всех возможных длин от трёх до числа вершин графа. Панциклические графы являются обобщением гамильтоновых графов, графов, которые имеют циклы максимальной возможной длины.
В теории графов говорят, что граф G гипогамильтонов, если сам по себе граф не имеет гамильтонова цикла, но любой граф, полученный удалением одной вершины из G, является гамильтоновым.
Гипотеза Барнетта — нерешённый вопрос в теории графов о существовании гамильтоновых циклов в графах. Гипотеза названа именем Дэвида В. Барнетта, эмерита калифорнийского университета в Дейвисе. Гипотеза утверждает, что любой двудольный граф многогранника с тремя рёбрами в каждой вершине имеет гамильтонов цикл.
Однозначно раскрашиваемый граф — это k-цветный граф, допускающий только одну (правильную) k-раскраску.
Степень k неориентированного графа G — это другой граф, имеющий тот же самый набор вершин, и две вершины этого графа смежны, если расстояние между этими вершинами в исходном графе G не превышает k. Для указания степени графа используется терминология, аналогичная степеням чисел — G2 называется квадратом графа G, G3 называется кубом.
Гипотеза Албертсона — недоказанная связь между числом пересечением и хроматическим числом графа. Гипотеза носит имя Михаила О. Албертсона, профессора колледжа Смит, который сформулировал утверждение в качестве гипотезы в 2007. Гипотеза является одной из многих гипотез в теории раскраски графов. Гипотеза утверждает, что среди всех графов, требующих n цветов, полный граф Kn находится среди графов, имеющих наименьшее число пересечений. Эквивалентно, если граф может быть нарисован с меньшим числом пересечений, чем у Kn, тогда, согласно гипотезе, его можно раскрасить в меньше чем n цветов.
Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь или гамильтонов цикл в заданном графе. Обе задачи NP-полны.
Планарное накрытие конечного графа G — это конечный накрывающий граф графа G, являющийся планарным графом. Любой граф, который может быть вложен в проективную плоскость, имеет планарное накрытие. Нерешённая гипотеза Сэйи Негами утверждает, что только эти графы и имеют планарные накрытия.
Периферийный цикл в неориентированном графе — цикл, который, неформально говоря, не отделяет любую часть графа от любой другой. Периферийные циклы, первым изучал Татт, Уильям Томас. Они играют важную роль в описании планарных графов и в образовании циклических пространств непланарных графов.
Квадратичный граф — граф, в котором все вершины имеют степень 4. Другими словами, квадратичный граф является 4-регулярным графом.
Пространство циклов неориентированного графа — линейное пространство над полем 
, состоящее из его эйлеровых подграфов. Размерность этого пространства называется контурным рангом графа. С точки зрения алгебраической топологии циклическое пространство является первой группой гомологий графа.
Гипотеза Харборта утверждает, что любой планарный граф имеет планарное представление, в котором каждое ребро является отрезком целочисленной длины. Эта гипотеза носит имя Хайко Харборта и усилила бы теорему Фари о существовании рисунка с прямолинейными рёбрами для любого планарного графа. По этой причине рисунок графа с целочисленными длинами рёбер известен также как целочисленное вложение Фари. Не смотря на многочисленные исследования в этом направлении гипотеза остаётся открытой.
