Yashiklar prinsipi

1- натижа. Боғламли граф ярим эйлер графи бўлиши учун ундаги иккитадан кўп бўлмаган учларнинг даражалари тоқ бўлиши зарур ва етарлидир.
Исботи 1- теореманинг исботидан баъзи ўзгартиришлар натижасида ҳосил қилиниши мумкин. ■
1- теорема асосида Кёнигсберг кўприклари ҳақидаги масаланинг (ушбу бобнинг 1- параграфига қаранг) ечими мавжуд эмас деган хулосага келамиз, яъни Кёнигсберг шаҳрининг ихтиёрий қисмида жойлашган уйдан чиқиб Прегел дарёси устига қурилган еттита кўприклардан фақат бир мартадан ўтган ҳолда, яна ўша уйга қайтиб келиш мумкин эмас.
Ориентирланган графларда ориентирланган эйлер йўлини излаш билан шуғулланиш мумкин. Ҳар бир ёйдан фақат бир марта ўтадиган йўл ориентирланган эйлер йўли деб аталади. Таркибида ориентирланган эйлер йўли бор бўлган ориентирланган граф ориентирланган эйлер графи деб аталади.
Енди қирралари сони га тенг бўлган берилган эйлер графида эйлер занжирини тузишнинг Флёри алгоритмини келтирамиз. Бу алгоритмга кўра графнинг қирралари эйлер циклида учраши тартиби бўйича 1дан гача рақамлаб чиқилади.
Берилган эйлер графи учун Флёри алгоритмига биноан қуйидаги иккита қоида асосида ишлар кетма-кет бажарилади:
1. Графнинг ихтиёрий учидан бошлаб бу учга инсидент бўлган исталган қиррага (масалан, қиррага) 1 рақами берилади. Бу қирра графдан олиб ташланади ва учдан учга (яъни олиб ташланган қиррага инсидент учга) ўтилади.
2. Охирги ўтишдан олдинги ўтиш натижасида ҳосил бўлган уч бўлсин ва охирги ўтишда бирор қиррага рақами берилган дейлик. учга инсидент исталган қирра имконияти борича шундай танланадики, бу қиррани олиб ташлаш графдаги боғламлиликни бузмасин. Танланган қиррага навбатдаги ( ) рақами берилади ва бу қирра графдан олиб ташланади. ■
Флёри алгоритмига кўра иш юритиш эйлер графи учун доимо чекли жараён эканлиги ва бу жараён доимо графдан барча қирраларнинг олиб ташланиши, яъни эйлер занжирини тузиш билан тугаши исботланган. Шуни ҳам таъкидлаш керакки, Флёри алгоритмини қўллаш жараёнида қирраларни танлаш имкониятлари кўп бўлгани учун, бундай вазиятларда, алгоритмни қўллаш мавжуд эйлер циклларидан бирини топиш билан чекланади. Тушунарлики, Флёри алгоритмини такрор қўллаб (бунда қирраларни танлаш жароёни алгоритмини аввалги қўллашлардагидек айнан такрорланмаслиги керак) графда мавжуд бўлган барча эйлер циклларини топиш мумкин.