Yashiklar prinsipi

Исботи. Зарурлиги. эйлер графида – эйлер цикли бўлсин. У ҳолда цикл бўйлаб ҳаракатланганда графнинг ҳар бир учидан ўтиш учун бир жуфт қиррадан фойдаланилади – бу қирралардан бири учга кириш учун, иккинчиси эса учдан чиқиш учун зарур бўлади. Бу ерда ҳар бир уч даражасининг жуфтлиги циклдаги ҳар бир қирранинг бир марта учраши мумкинлигидан келиб чиқади.
Етарлилиги. Энди графнинг ҳар бир учи даражаси жуфт бўлсин деб фараз қиламиз. граф боғламли бўлгани учун ундаги ҳар бир учнинг даражаси иккидан кичик эмас. Маълумки, агар графда ҳар бир учнинг даражаси иккидан кичик бўлмаса, у ҳолда бундай граф таркибида цикл мавжуд (ушбу бобнинг 4- параграфидаги 1- теоремага қаранг).
Демак, графнинг қирраларидан ташкил этилган қандайдир цикл бор. Бу циклни унинг ихтиёрий учидан бошлаб қурамиз. Дастлаб учга инсидент бўлган ихтиёрий бир қиррани танлаб, бу қирра бўйлаб ҳаракатланамиз ва унинг бошқа учига ўтамиз. Ҳар сафар, имконияти борича, янги қирра танлаб ва бу қиррадан ўтиб унинг бошқа учига борамиз. Шуни таъкидлаш зарурки, бундай ўтислар жараёнида фақат қирранинг янгисини танлашга ҳаракат қилинади, учлар эса исталганча такрорланишлари мумкин.
Ҳар бир учга инсидент қирралар сони жуфт бўлгани учун циклни қуриш жараёни фақат учга боргандагина тугайди. Бу ерда икки ҳол бўлиши мумкин:
1) цикл графнинг барча қирраларидан ўтади, ёки
2) цикл графнинг барча қирраларидан ўтмайди. Биринчи ҳолда теорема исботланди дейиш мумкин. Иккинчи ҳолда графдан циклга тегишли барча қирраларни олиб ташлаймиз ва натижада ҳосил бўлган графни деб белгилаймиз. Бу ерда яккаланиб қолган учларни олиб ташлаш ёки олиб ташламаслик муҳим эмас. Агар яккаланиб қолган учлар олиб ташланмаса, натижада боғламли бўлмаган графни ҳосил қи-лишимиз ҳам мумкин. Графдан қирраларни бундай олиб ташлаш амали, табиийки, графнинг қирралари сонини камайтиради, лекин графдаги учларнинг даражалари жуфтлиги хоссасини ўзгартирмайди.
графнинг боғламлилигига кўра цикл ва граф ҳеч бўлмаса битта умумий учга эга бўлишлари керак. Шу сабабли, циклда графнинг қирраларига ҳам инсидент бўлган қандайдир уч бор. Бу учдан бошлаб фақат графнинг қирраларидан ташкил топган янги циклни қуриш мумкин. циклни қуриш жараёни фақат учга келиб тугаши мумкин.
Олдин қурилган циклни икки қисмга ажратамиз:
1) циклнинг учидан бошланиб учида туговчи қисми (бу оддий занжирни билан белгилаймиз) ва
2) циклнинг учидан бошланиб учида туговчи қолган қисми ( ).
У ҳолда учдан бошлаб занжирнинг қирралари бўйлаб учга борувчи, кейин циклнинг барча қирраларидан ўтувчи ва, ниҳоят, занжирнинг қирралари бўйлаб учга қайтиб келувчи янги

циклни ҳосил қилиш мумкин.
Агар цикл эйлер цикли бўлса, теореманинг тасдиғи исботланди деса бўлади. Акс ҳолда юқорида баён этилган жараённи такрорлаймиз.
Берилган графдаги қирралар сони чекли бўлганлигидан, бу жараён чекли жараёндир. Бу жараённи етарлича такрорлагандан сўнг, албатта, у эйлер циклини қуриш билан якунланади. ■