Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.
Теорема Фа́ри — теоретико-графовое утверждение о возможности выпрямить рёбра любого планарного графа. Иными словами, разрешение рисовать рёбра не в виде отрезков, а в виде кривых, не расширяет класс планарных графов.
Граф Грёча — граф без треугольников с 11 вершинами, 20 рёбрами, хроматическим числом 4 и числом скрещиваний 5. Граф назван в честь немецкого математика Герберта Грёча и он демонстрирует необходимость предположения планарности в теореме Грёча, которая утверждает, что любой планарный граф без треугольников можно раскрасить в 3 цвета. Граф Грёча является членом бесконечной последовательности графов без треугольников, в которой каждый граф является мычельскианом предыдущего графа, начиная с нуль-графа. Эта последовательность графов была использована Мыцельским, чтобы показать, что существуют графы без треугольников с произвольно большим хроматическим числом. По этой причине иногда граф Грёча называют графом Мыцельского или Мыцельского-Грёча. В отличие от других, более поздних графов в последовательности, граф Грёча является наименьшим графом без треугольников с его хроматическим числом.
В теории графов графом без треугольников называется неориентированный граф, в котором никакие три вершины не образуют треугольник из рёбер. Графы без треугольников можно определить также как графы с кликовым числом ≤ 2, графы с обхватом ≥ 4, графы без порождённых 3-циклов, или как локально независимые графы.
Мычельскиан или граф Мычельского неориентированного графа — граф, созданный применением конструкции Мычельского . Конструкция сохраняет отсутствие треугольников, но увеличивает хроматическое число. Мычельский показал, что повторяя конструкцию повторно к начальному графу без треугольников, можно получить графы без треугольников произвольно большого размера.
Обобщённые графы Петерсена — семейство кубических графов, образованное соединением вершин правильного многоугольника с соответствующими вершинами звезды. В семейство входит граф Петерсена и обобщает один из путей построения графа Петерсена. Семейство обобщённых графов Петерсена ввёл в рассмотрение в 1950 году Коксетер и этим графам дал имя в 1969 году Марк Воткинс.
Снарк в теории графов — связный кубический граф без мостов c хроматическим индексом 4. Другими словами, это граф, в котором каждая вершина имеет три соседние вершины и рёбра нельзя выкрасить только в три цвета, так чтобы два ребра одного цвета не сходились в одной вершине. Чтобы избежать тривиальных случаев, снарками часто не считают графы, имеющие обхват меньше 5.
В теории графов снарки «Цветы» образуют бесконечное семейство снарков, введённых Айзексом Руфусом в 1975 году.
Жадная раскраска в теории графов — раскраска вершин неориентированного графа, созданная жадным алгоритмом, который проходит вершины графа в некоторой предопределённой последовательности и назначает каждой вершине первый доступный цвет. Жадные алгоритмы, в общем случае, не дают минимально возможное число цветов, однако они используются в математике в качестве техники доказательств других результатов, относящихся к раскраске, а также в компьютерных программах для получения раскраски с небольшим числом цветов.
Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.
В теории графов число пересечений cr(G) графа G — это наименьшее число пересечений рёбер плоского рисунка графа G. Например, граф является планарным тогда и только тогда, когда его число пересечений равно нулю.
В теории графов граф Титце — это неориентированный кубический граф с 12 вершинами и 18 рёбрами. Граф назван именем Генриха Титце, показавшего в 1910 году, что ленту Мёбиуса можно разделить на шесть областей, касающихся друг друга — три вдоль границы ленты и три вдоль центральной линии — а потому для графов, допускающих вложение в ленту Мёбиуса, может потребоваться шесть цветов. Граничные сегменты областей Титца разделения ленты Мёбиуса образуют вложение графа Титце.
В теории графов говорят, что граф G гипогамильтонов, если сам по себе граф не имеет гамильтонова цикла, но любой граф, полученный удалением одной вершины из G, является гамильтоновым.
Многогранник Кли — конструкция позволяющая получить новый многогранник по данному. Названа в честь американского математика Виктора Кли
Граф Аполлония — неориентированный граф, образованный рекурсивным процессом подразделения треугольника на три меньших треугольника. Графы Аполлония можно эквивалентно определить как планарные 3-деревья, как максимальные планарные хордальные графы, как однозначно 4-раскрашиваемые планарные графы или как графы блоковых многогранников. Графы названы именем Аполлония Пергского, изучавшего связанные построения упаковки кругов.
Гусеница или гусеничное дерево — это дерево, в котором все вершины находятся на расстоянии не более 1 от центрального пути.
Универсальный граф — это бесконечный граф, содержащий любой конечный граф в качестве порождённого подграфа. Универсальный граф этого типа первым построил Р. Радо и этот граф теперь называется графом Радо или случайным графом. Более свежие работы фокусируются на универсальных графах для семейства графов F. То есть бесконечный граф, принадлежащий F, содержащий все конечные графы семейства F. Например, графы Хэнсона являются универсальными в этом смысле для графов без i-клик.
Граф дружеских отношений Fn — это планарный неориентированный граф с 2n+1 вершинами и 3n рёбрами.
Граф Винера — Арайи — граф с 42 вершинами и 67 рёбрами. Он гипогамильтонов, что означает, что сам по себе он не имеет гамильтонова цикла, но любой граф, образованный удалением отдельной вершины, гамильтонов. Он также планарен.
