Ейлеровим називається цикл в графі, що містить всі ребра графа.
Ейлеровим графом називається зв'язний граф, в якому є ейлерову цикл. Ейлерову граф можна намалювати, не відриваючи олівця від паперу і не повторюючи ліній (рис. 14).
Мал. 14. Ейлеров граф
Теорема 6. Граф G є ейлерову тоді і тільки тоді, коли G - зв'язний граф, що мають всі парні вершини.
Гамільтонової ланцюгом називається простий ланцюг, що містить всі вершини графа.
Гамільтоновим циклом називається Гамільтона ланцюг, початок і кінець якої збігаються.
Граф називаетсягамільтоновим, якщо в ньому є гамільтонів цикл (рис.15).
Мал. 15. Гамильтонов граф
Граф G називають p - хроматичним, де p - натуральне число, якщо його вершини можна розфарбувати p - різними кольорами так, щоб ніякі дві суміжні вершини не були розфарбовані однаково.
Найменше число р, при якому граф є р - хроматичним, називають хроматичним числом графа і позначають. Якщо = 2, то граф називається біхроматичним. Необхідною і достатньою умовою в графі циклів непарної довжини.
Наприклад, граф на рис. 16 біхроматична, його вершини "розфарбовані" двома "квітами", позначеними 0 і 1.
Мал. 16. біхроматична граф.
Плоскі і планарні графи
Граф G називається планарним (плоским), якщо існує ізоморфний йому граф G ', в зображенні якого на площині ребра перетинаються тільки у вершинах. Іншими словами, у планарного графа ніякі два ребра не мають спільних точок, крім загальних вершин. Наприклад, граф на рис. 5 є планарним, а на рис. 7 - немає.
Теорема Ейлера. Зв'язний плоский граф з n вершинами і m ребрами розбиває площину на k областей (включаючи і зовнішню), причому
Граф називається дводольним, якщо безліч його вершин X може бути розділене на два непересічних підмножини таким чином, що кожне ребро графа з'єднує вершини з двох різних підмножин.