Yashiklar prinsipi

8- теорема (Д. Кёниг). Графнинг икки бўлакли бўлиши учун унинг таркибида узунлиги тоқ сон билан ифодала-нувчи сикл бўлмаслиги зарур ва етарлидир.
Исботи ўқувчига ҳавола қилинади. ■
Берилган графнинг икки бўлаклилигини аниқлашнинг содда усули бор. Бу усул кўндалангига излаш деб аталувчи соддагина излаш ғоясига асосланган.
Кўндалангига излаш усулига кўра графнинг учлари рақамлар билан қуйдаги қоида бўйича белгиланади. Дастлаб графнинг ихтиёрий учи 0 рақами билан белгилаб олинади. Шу 0 белгили учга қўшни барча учларга 1 белгиси қўйилади. Энди 1 белгили ҳар бир учга қўшни учларни аниқлаб, улар орасидаги белгиси йўқ учларга 2 белгисини қўаймиз. Кейин 2 белгисига эга барча учларни аниқлаб, улар учун ҳам юқоридагига ўхшаш иш юритамиз. Бу жараённи мумкин бўлган қадар давом эттирамиз. Тушунарлики, агар граф боғламли бўлса, у ҳолда кўндалангига излаш усули графнинг барча учларини рақамлаб чиқиш имконини беради.

Боғламли граф учларини белгилаш жараёни тугагандан сўнг, унинг учлари тўплами ни иккита ва тўпламга қуйидагича ажратамиз: жуфт рақамли учларни тўпламга, қолган учларни эса тўпламга киритамиз (0 рақамли уч тўпламга киритилади). графнинг иккала учи ҳам тўпламга тегишли барча қирралари кортежини билан, унинг иккала учи ҳам тўпламга тегишли барча қирралари кортежини эса билан белгилаймиз. Агар ва кортежлар бўш бўлса, у ҳолда берилган граф икки бўлаклидир, акс ҳолда у икки бўлакли эмас.

Ҳозиргача бўлган ҳол учун графнинг бўлаклилигини аниқлаш бўйича оддий усул топилмаган.
Глоссарий

Термин	Ўзбек тилидаги шархи
Маршрут	графдаги учлар ва қирраларнинг ҳар икки қўшни қирралари умумий четки учга эга кўринишдаги чекли ёки чексиз кетма-кетлиги графдан қиррани иккига бўлиш амалини чекли марта кетма-кет қўллаш воситасида ҳосил қилинган граф
Бошланғич учи	маршрутда қандайдир учдан олдин учлар мавжуд бўлмаган уч.
Охирги учи	шу учдан кейин маршрутга тегишли учлар бўлмаган уч
Йўналган маршрут	Агар маршрутнинг бошланғич учи ва охирги учи бўлса, у ҳолда уни учдан учга йўналган маршрут.
Икки томонлама чексиз маршрут	бошланғич учга ҳам охирги учга ҳам эга бўлмаган маршрут.
Тривиал маршрут	бирорта ҳам қиррага эга бўлмаган маршрут.