Граф є дводольним тоді і лише тоді, коли він 2-хроматичний; тобто його хроматичне число дорівнює двом. елементами іншої (Теорема про весілля). Повний дводольний граф, У якого в кожній частині більше 2 вершин, є непланарним. Будь-який дводольний граф є досконалим.

Визначення дводольного графа Розбиття графа на дві частки називається фарбуванням його вершин у два різні кольори. Кожне ребро має поєднувати вершини різного кольору. Існує ще одна ознака дводольності графа: граф є дводольним і тоді, коли у ньому відсутні цикли непарної довжини.

Простий граф — граф, в якому немає кратних ребер та петель. Простий шлях – шлях, всі вершини якого попарно різні. Іншими словами, простий шлях не проходить двічі через одну вершину.