Тут зібрані визначення термінів із теорії графів. Курсивом позначені посилання на терміни в цьому словнику (на цій сторінці).

А Автоморфізм — ізоморфізм графа із самим собою. Алгебрична зв'язність — друге з найменших власних значень матриці Кірхгофа графа.

Б Багаточастковий граф — граф, множину вершин якого можна розбити на k незалежних множин (часток). Біграф — див. двочастковий граф. Блок-схема із параметрами (v, k, λ) — покриття з кратністю λ повного графа на v вершинах повними графами на k вершинах. Блоковий граф — вид неорієнтованого графа, в якому кожна компонента двозв'язності (блок) є клікою.

В Валентність вершини — див. Степінь вершини Вершина, Вузол — базове поняття: точка, де можуть сходитися/розходитися ребра та/або дуги. Множина вершин графа G позначається V(G) Висяча вершина — вершина, степінь якої дорівнює 1 (тобто ) Вага ребра — значення, поставлено у відповідність даному ребру зваженого графа. Зазвичай вага — дійсне число, в такому випадку його можна інтерпретувати як «довжину» ребра. Відстань між двома вершинами графа — найменша довжина шляху, що з'єднує ці вершини. Впорядкований граф — граф, в якому ребра, що виходять з кожної вершини, однозначно пронумеровані, починаючи з 1. Ребра вважаються впорядкованими в порядку зростання номерів. При графічному представленні часто ребра вважаються впорядкованими в порядку певного стандартного обходу (наприклад, проти годинникової стрілки). Вузол — те саме, що і Вершина.

Г Гамільтонів граф — граф, в якому є гамільтонів цикл. Гамільтонів шлях — простий шлях в графі, що містить всі вершини графа точно по одному разу. Гамільтонів цикл — простий цикл в графі, що містить всі вершини графа точно по одному разу. Гармонійне розфарбування — це (правильне) розфарбування вершин, за якого будь-яка пара кольорів з'являється на суміжних вершинах не більше одного разу. Геометрична реалізація — фігура, вершинам якої відповідають вершини графа, ребрам — ребра графа, і ребра у фігурі поєднують вершини, що відповідають вершинам в графі. Геометричний граф — плоска фігура з вершин — точок площини і ребер — ліній, що з'єднують деякі пари вершин. Може зображати багатьма способами будь-який граф. Гіперграф — сукупність із множини вершин і множини гіперребер (підмножина n-го евклідового степеня множини вершин, тобто гіперребра об'єднують довільну кількість вершин). Гомеоморфні графи — графи, отримані з одного графа за допомогою послідовного підрозбиття ребер. Грань — область, обмежена ребрами в плоскому графі, і така, що не містить всередині себе вершин і ребер графа. Зовнішня частина площини також утворює грань. Граф — базове поняття. Містить в собі множину вершин і множину ребер, що являє собою підмножину декартового добутку множини вершин (тобто кожне ребро з'єднує рівно дві вершини). Граф роду g — граф, який можна зобразити без перетинань на поверхні роду g і не можна зобразити без перетинань на жодній поверхні роду g-1.

Д Двоїстий граф. Граф А називається двоїстим до планарного графа В, якщо вершини графа А відповідають граням графа В, і дві вершини графа A з'єднані ребром тоді і тільки тоді, коли відповідні грані графа B мають хоча б одне спільне ребро. Двочастковий граф або дводольний граф (або біграф, або парний граф) — граф , такий що множина вершин V розбита на дві підмножини і , що не перетинаються, при чому кожне ребро E інцидентне вершині з і вершині з (тобто з'єднує вершину з з вершиною з ). Тобто, існує правильне разфарбування графа двома кольорами. Множини і називають «долями» двочасткового графа. Двочастковий граф називается «повним», якщо будь-які дві вершини з і виявляться суміжними. Якщо , , то повний двочастковий граф позначається . Деревний кістяк — кістякове піддерево графа , в якому відстань між будь-якою парою вершин не перевищує -разової відстані між ними у графі . Дерево — зв'язний граф, що не містить циклів. Діаметр графа — максимальна відстань між вершинами для всіх пар вершин. Відстань між вершинами — найменша кількість ребер шляху, що з'єднує дві вершини. Довжина маршрута — кількість ребер в маршруті (з повтореннями). Якщо маршрут , то довжина M дорівнює k (позначається ). Довжина шляху — кількість дуг шляху (або сума довжин його дуг, якщо останні задані). Так для шляху v1, v2, …, vn довжина дорівнює n-1. Доповнення графа — граф над тою самою множиною вершин, що і початковий, але вершини з'єднані ребрами тоді і тільки тоді, коли в початковому графі ребра немає. Дуга — орієнтоване ребро.

Е Евклідове мінімальне кістякове дерево Ейлерів граф — граф, в якому існує цикл, що містить усі ребра графа по одному разу, вершини можуть повторюватися. Ейлерів ланцюг (або Ейлерів цикл) — ланцюг (цикл), що містить всі ребра графа, вершини можуть повторюватися. Екстремальна теорія графів  — максимальна відстань від заданої вершини до будь-якої іншої. Елементарний шлях — шлях, вершини якого, за виключенням можливо, першої і останньої, різні. Іншими словами, простий шлях не проходить двічі через одну вершину, але може починатися і закінчуватися в тій самій вершині, в такому випадку він називається циклом (елементарним циклом). Елементарним стягуванням називається така процедура: беремо ребро (разом інцидентними йому вершинами вершинами, наприклад, u і v) і «стягуємо» його, тобто видаляємо ребро і ототожнюємо вершини u і v. Утворена вершина інцидентна ребрам, яким початково були інцидентні u або v крім видаленого.

З Зважений граф — граф, кожному ребру якого поставлено у відповідність деяке значення (вага ребра). Зв'язність. Дві вершини в графі зв'язні, якщо існує (простий) ланцюг, що їх з'єднує. Зв'язний граф — граф, в якому всі вершини зв'язані. Граф-зірка — повний двочастковий граф . Змішаний граф — граф, що містить як орієнтовані, так і неорієнтовані ребра.

І Ізольована вершина — вершина, степінь якої дорівнює 0 (тобто не існують ребра інцидентні до неї). Ізоморфізм. Два графи називаються ізоморфними, якщо існує перестановка вершин, при якій вони збігаються. Іншими словами, два графи називаються ізоморфними, якщо існує взаємооднозначна відповідність між їх вершинами і ребрами, така що зберігається суміжність та інцидентність. Інваріант — функція на множині графів, постійна на класах ізоморфних графів. Індекс доступності вершини (K) — Ki = (ΣL)i / (ΣL)min, де ΣL — сума найкоротших віддалей вершини. Див. також Центральність за близькістю. Інтервальний граф — граф, вершини якого можуть бути поставлені у відповідність відрізкам на дійсній осі таким чином, що дві вершини інцидентні одному ребру тоді і тільки тоді, коли відрізки, що відповідають цим вершинам, перетинаються. Інцидентність — поняття, що використовується тільки для ребра і вершини: якщо  — вершини, а  — ребро, що їх з'єднує, тоді вершина і ребро e інцидентні, вершина і ребро e також інцидентні. Дві вершини (або два ребра) інцидентними бути не можуть. Для позначення найближчих вершин (ребер) використовується поняття суміжності.

К Каркасний підграф — підграф, що містить всі вершини. Кінець нескінченного графа, це клас еквівалентності променів, в якому два промені еквівалентні, якщо існує третій промінь, який містить нескінченно багато вершин цих графів. Кістякове (каркасне) дерево зв'язного графа G=(V, E) це таке дерево T=(V, ET), що ET ⊆ E. Кістяковим (каркасним) лісом незв'язного графа G=(V, E) називають сукупність кістякових (каркасних) дерев компонент зв'язності графа G. Кліка — підмножина вершин графа, повністю з'єднаних кожна з кожною, тобто підграф, що являє собою повний граф. Клікова ширина — параметр, який описує структурну складність графа. Клікове дерево — див. Блоковий граф. Клікове число (Clique number) — число (G) вершин в найбільший кліці. Інші назви — густота, щільність. Максимальна кліка — кліка з максимально можливою кількістю вершин графа. Клітка — регулярний граф найменшого обхвату для заданого степеня вершин. Коефіцієнт галуження — кількість прямих нащадків у кожному вузлі дерева. Коефіцієнт сітчастості — інваріант планарних графів. Компонента зв'язності графа — деяка підмножина вершин графа така, що для будь-яких двох вершин із цієї множини існує шлях із однієї в іншу, і не існує шляху з вершини цієї множини в вершину не з цієї множини. Компонента сильної зв'язності графа, шар — максимальна множина вершин орієнтованого графа така, що для будь-яких двох вершин із цієї підмножини існує шлях як із першої в другу, так і навпаки. Конструктивний перерахунок графів — отримання повного списку графів у заданому класі. Контур — замкнений шлях в орграфі. Косе розбиття — розбиття вершин графа на дві підмножини у вигляді незв'язного породженого підграфа та доповнення. Коцикл — мінімальний розріз, мінімальна множина ребер, видалення якої робить граф незв'язним. Кратні ребра — декілька ребер, інцидентних одній і тій самій парі вершин. Зустрічаються в мультиграфах. Кубічний граф — регулярний граф степеня 3, тобто граф, в якому кожній вершині інцидентні рівно три ребра. k-дольний граф — граф G, у якого хроматичне число c(G)=k

Л Лама́нів граф з n вершинами — такий граф G, що, по-перше, для кожного k будь-який підграф графа G, що містить k вершин, має не більше, ніж 2k −3 ребра і, по-друге, граф G має рівно 2n −3 ребра. Лінійна деревність — найменша кількість лінійних лісів, на які можна розбити граф. Лінійний ліс — ліс, утворений з диз'юнктного об'єднання шляхів Ліс — неорієнтований граф без циклів. Компонентами зв'язності лісу є дерева. Ланцюг в графі — маршрут, всі ребра якого різні. Якщо всі вершини (а таким чином і ребра) різні, то такий ланцюг називається простим (елементарним). В ланцюзі вершини і називаються кінцями ланцюга. Ланцюг із кінцями u і v з'єднує вершини u і v. Ланцюг, що з'єднує вершини u і v позначається . Для орграфів ланцюг називається орланцюгом. В деяких джерелах простий ланцюг — ланцюг, ребра якого різні, що є слабкою умовою.

М Маршрут (теорія графів)В різних джерелах надають різні визначення маршруту, шляху, ланцюга, їх простоти та елементарності. в графі — послідовність вершин і ребер , що чергуються, в якій будь-які два сусідні елемента інцидентні. Якщо , то маршрут замкнений, інакше відкритий. Матриця досяжності орграфа — матриця, що містить інформацію про існування шляхів між вершинами орграфа. Матриця інцидентності графа — матриця, значення елементів якої характеризуються інцидентністю відповідних вершин графа (по вертикалі) та його ребер (по горизонталі). Для неорієнтованого графа елемент приймає значення 1, якщо вершина і ребро, що відповідають йому, інцидентні. Для орієнтованого графа елемент приймає значення 1, якщо інцидентна вершина є початок ребра, значення -1, якщо кінець; в інших випадках (в тому числі і для петель) значенню елемента присвоюється 0. Матриця суміжності графа — матриця, значення елементів якої характеризується суміжністю вершин графа. При цьому, значенню елемента матриці присвоюється кількість ребер, які з'єднують відповідні вершини (тобто які інцидентні обом вершинам). Петля вважається одразу двома з'єднаннями для вершини, тобто до значення елемента матриці в такому випадку треба додавати 2. Мережа — в принципі, те саме що і граф, хоча мережами зазвичай називають графи, вершини яких визначеним способом позначені. Мінімальний каркас (або Каркас мінімальної ваги, Мінімальне кістякове дерево) графа — ациклічна множина ребер в зв'язному, зваженому і неорієнтованому графі, що з'єднує між собою всі вершини цього графа, при цьому сума ваг усіх ребер у ньому мінімальна. Міст — ребро, видалення якої збільшує кількість компонент зв'язності. Рівнозначне визначення, ребро є мостом тоді і тільки тоді, коли вони не є частиною будь-якого циклу. Множина домінування — така множина вершин графа, що кожна вершина графа або належить їй, або суміжна деякій вершині, що належить множині домінування. Множина суміжності вершини v — множина вершин, суміжних із вершиною v. Позначається