Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
Кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром. Клики являются одной из основных концепций теории графов и используются во многих других математических задачах и построениях с графами. Клики изучаются также в информатике — задача определения, существует ли клика данного размера в графе является NP-полной. Несмотря на эту трудность, изучаются многие алгоритмы для поиска клик.
В теории графов граф называется хордальным, если каждый из его циклов, имеющих четыре ребра и более, имеет хорду.
В теории графов смежной вершиной вершины v называется вершина, соединённая с v ребром. Окрестностью вершины v в графе G называется порождённый подграф графа G, состоящий из всех вершин, сопряжённых v и всех рёбер, соединяющих две такие вершины. Например, рисунок показывает граф с 6 вершинами и 7 рёбрами. Вершина 5 смежна вершинам 1, 2 и 4, но не смежна вершинам 3 и 6. Окрестность вершины 5 — это граф с тремя вершинами 1, 2 и 4, и одним ребром, соединяющим вершины 1 и 2.
В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).
В теории графов расщепляемым графом называется граф, в котором вершины можно разделить на клику и независимое множество. Расщепляемые графы впервые изучали Фёлдес и Хаммер, и независимо ввели Тышкевич и Черняк.
В теории графов древесная ширина неориентированного графа — это число, ассоциированное с графом. Древесную ширину можно определить несколькими эквивалентными путями: как размер наибольшего множества вершин в древесном разложении, как размер наибольшей клики в хордальном дополнении графа, как максимальный порядок убежища при описании стратегии игры преследования на графе или как максимальный порядок ежевики, набора связных подграфов, которые касаются друг друга. Древесная ширина часто используется в качестве параметра в анализе параметрической сложности алгоритмов на графах. Графы с шириной дерева, не превосходящей k, называются частичными k-деревьями. Многие другие хорошо изученные семейства графов также имеют ограниченную ширину дерева.
Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.
В теории графов хорошо покрытый граф — это неориентированный граф, в котором все минимальные по включению вершинные покрытия имеют один и тот же размер. Хорошо покрытые графы определил и изучал Пламмер.
В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.
Теорема Вагнера — характеризация планарных графов тесно связанная с теоремой Понтрягина — Куратовского.
Гипотеза Барнетта — нерешённый вопрос в теории графов о существовании гамильтоновых циклов в графах. Гипотеза названа именем Дэвида В. Барнетта, эмерита калифорнийского университета в Дейвисе. Гипотеза утверждает, что любой двудольный граф многогранника с тремя рёбрами в каждой вершине имеет гамильтонов цикл.
Граф Аполлония — неориентированный граф, образованный рекурсивным процессом подразделения треугольника на три меньших треугольника. Графы Аполлония можно эквивалентно определить как планарные 3-деревья, как максимальные планарные хордальные графы, как однозначно 4-раскрашиваемые планарные графы или как графы блоковых многогранников. Графы названы именем Аполлония Пергского, изучавшего связанные построения упаковки кругов.
Теорема о совершенных графах Ловаша утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно. Это утверждение высказал в виде гипотезы Берж и утверждение называют иногда слабой теоремой о совершенных графах, чтобы не смешивать со строгой теоремой о совершенных графах, описывающей совершенные графы их запрещёнными порождёнными подграфами.
Критерий планарности Маклейна — это описание планарных графов в терминах их пространства циклов. Критерий носит имя Саундерса Маклейна, опубликовавшего критерий в 1937. Критерий утверждает, что конечный неориентированный граф является планарным тогда и только тогда, когда пространство циклов графа имеет базис циклов, в котором каждое ребро графа принадлежит не более чем двум базисным векторам.
Косое разбиение графа — разбиение его вершин на два подмножества в виде несвязного порождённого подграфа и дополнения; играет важную роль в теории совершенных графов.
Периферийный цикл в неориентированном графе — цикл, который, неформально говоря, не отделяет любую часть графа от любой другой. Периферийные циклы, первым изучал Татт, Уильям Томас. Они играют важную роль в описании планарных графов и в образовании циклических пространств непланарных графов.
