Двочастковий граф

Повний дводольний граф ${\displaystyle K_{3,2}}$

Неорієнтовний граф ${\displaystyle G=(W,E)\,}$ називається дводольним, якщо множина його вершин розбита на дві підмножини ${\displaystyle U\cup V=W\quad |U|>0,|V|>0,}$ так, що

• жодна вершина в ${\displaystyle U\,}$ не з'єднана з вершинами в ${\displaystyle U\,}$ і
• жодна вершина в ${\displaystyle V\,}$ не з'єднана з вершинами в ${\displaystyle V\,}$

Дводольний граф називається повним, якщо для кожної пари вершин ${\displaystyle u\in U,v\in V}$ існує ребро ${\displaystyle (u,v)\in E}$. Для

${\displaystyle |U|=i,|V|=j\,}$

такий граф позначається ${\displaystyle K_{i,j}\,}$

• Граф є дводольним тоді й лише тоді, коли він не містить циклів непарної довжини.
• Граф є дводольним тоді й лише тоді, коли його хроматичне число дорівнює 2

• Усі дерева є дводольними графами.
• Цикли з парною кількістю вершин є дводольними графами.
• Планарний граф у якого всі грані мають парну кількість ребер.

• Теорема Холла
• Двочасткова розмірність
• Майже многокутник

• Chartrand, G. Introductory Graph Theory. New York: Dover, 1985.
• Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.