В теории графов граф называется хордальным, если каждый из его циклов, имеющих четыре ребра и более, имеет хорду.
Пло́тный граф — граф, в котором число рёбер 
близко к максимально возможному у полного графа с числом вершин 
:
В теории графов порождённым путём в неориентированном графе G называется путь, являющийся порождённым подграфом G. Таким образом, это последовательность вершин в G такая, что любые две смежные вершины в последовательности соединены ребром в G, и любые две несмежные вершины последовательности не соединены ребром G. Порождённый путь иногда называют змеёй и задача поиска самого длинного порождённого пути в графах гиперкубов известна как задача о змее в коробке.
В теории графов древесная ширина неориентированного графа — это число, ассоциированное с графом. Древесную ширину можно определить несколькими эквивалентными путями: как размер наибольшего множества вершин в древесном разложении, как размер наибольшей клики в хордальном дополнении графа, как максимальный порядок убежища при описании стратегии игры преследования на графе или как максимальный порядок ежевики, набора связных подграфов, которые касаются друг друга. Древесная ширина часто используется в качестве параметра в анализе параметрической сложности алгоритмов на графах. Графы с шириной дерева, не превосходящей k, называются частичными k-деревьями. Многие другие хорошо изученные семейства графов также имеют ограниченную ширину дерева.
Блоковый граф — вид неориентированного графа, в котором каждая компонента двусвязности (блок) является кликой.
Комбинаторика многогранников — это область математики, принадлежащая комбинаторике и комбинаторной геометрии и изучающая вопросы подсчёта и описания граней выпуклых многогранников.
Фасета в геометрии — элемент многогранника или связанной геометрической структуры, как правило на единицу меньшей размерности самой структуры.
- В трёхмерном пространстве фасета многогранника — любой многоугольник, вершины которого являются вершинами многогранника, но который сам не является гранью. Огранка многогранника — нахождение и объединение фасет, которые образуют новый многогранник. Процесс является обратным образованию звёздчатой формы и может быть применён к многогранникам высоких размерностей.
- В комбинаторике многогранников и общей теории многогранников фасета многогранника размерности n — грань, имеющая размерность n−1. Фасеты можно назвать (n−1)-гранями или гипергранями. В трёхмерной геометрии они часто называются «гранями» без дальнейших уточнений.
- Фасета симплициального комплекса — максимальный симплекс, не являющейся гранью другого симплекса комплекса. Для симплициальных многогранников это совпадает с комбинаторным определением.
В теории графов глубина дерева связного неориентированного графа G — это числовой инвариант G, минимальная высота дерева Тремо для суперграфа графа G. Этот инвариант и близкие понятия встречаются под различными именами в литературе, включая число ранжирования вершин, упорядоченное хроматическое число и минимальная высота исключения дерева. Понятие близко также к таким понятиям, как циклический ранг ориентированных графов и высота итерации языка регулярных языков. Интуитивно, если древесная ширина графа измеряет, насколько граф далёк от дерева, глубина дерева измеряет, насколько граф далёк от звезды.
В теории графов путевая декомпозиция графа G — это, неформально, представление графа G в виде «утолщённого» пути, а путевая ширина графа G — это число, измеряющее, насколько граф G был утолщён. Более формально, путевая декомпозиция — это последовательности вершин подмножества графа G, такие, что конечные вершины каждого ребра появляются в одном из подмножеств и каждая вершина принадлежит одному из множеств, а путевая ширина на единицу меньше размера наибольшего множества в такой декомпозиции. Путевая ширина известна также как интервальная толщина, величина вершинного разделения или вершинно-поисковое число.
Число очередей графа — это инвариант графа, определённый аналогично стэковому числу и использующий упорядочение FIFO вместо упорядочения LIFO.
Граф Аполлония — неориентированный граф, образованный рекурсивным процессом подразделения треугольника на три меньших треугольника. Графы Аполлония можно эквивалентно определить как планарные 3-деревья, как максимальные планарные хордальные графы, как однозначно 4-раскрашиваемые планарные графы или как графы блоковых многогранников. Графы названы именем Аполлония Пергского, изучавшего связанные построения упаковки кругов.
Ациклическая ориентация неориентированного графа — это назначение направлений каждому ребру (ориентация), при которой не образуется какого-либо ориентированного цикла, а потому такая ориентация превращает граф в направленный ациклический граф. Любой граф имеет ациклическую ориентацию.
Теорема Галлаи – Хассе – Роя – Витавера — это вид двойственности между раскрасками вершин заданного неориентированного графа и ориентациями его рёбер. Теорема утверждает, что минимальное число красок, необходимых для правильной раскраски любого графа G, на единицу больше длины максимального пути в ориентации графа G, в которой эта длина пути минимальна. В ориентации, в которых путь максимальной длины имеет минимальную длину, всегда входит по меньшей мере одна ациклическая ориентация.
Блоковый многогранник — это (многомерный) многогранник, образованный из симплекса путём многократного приклеивания другого симплекса к одной из его фасет.
Говорят, что семейство графов имеет ограниченное расширение, если все его миноры ограниченной глубины являются редкими графами. Много естественных семейств редких графов имеют ограниченное расширение. Близкое, но более сильное свойство, полиномиальное расширение, эквивалентно существованию теорем разбиения для этих семейств. Семейства с этими свойствами имеют эффективные алгоритмы для задач, в которые входят задача поиска изоморфного подграфа и проверка моделей для теории первого порядка для графов.
Дерево Тремо неориентированного графа G — это остовное дерево графа G с выделенным корнем со свойством, что любые две смежные вершины в графе G связаны друг с другом отношением предок/потомок. Все деревья поиска в глубину и все гамильтоновы пути являются деревьями Тремо. Деревья Тремо названы именем Шарля Пьера Тремо, французского автора 19-го века, который использовал вариант поиска в глубину как стратегию выхода из лабиринта. Деревья Тремо также называют нормальными остовными деревьями, особенно в контексте бесконечных графов.
Ядро графа — это понятие, описывающее поведение графа в отношении гомоморфизмов графа.
