Yashiklar prinsipi

Исботи. Теореманинг 1) тасдиғидан унинг 2) тасдиғи келиб чиқишини исботлаймиз. граф дарахт бўлсин. Дарахтнинг таърифига кўра, у аЦиклик бўлишини таъкидлаб, бўйича математик индуксия усулини қўллаймиз.
Математик индуксия усулининг базаси: агар бўлса, у ҳолда дарахт фақат битта учдан ташкил топган бўлади. Табиийки, агар битта учга эга бўлган графда Цикл бўлмаса, у ҳолда унда бирорта ҳам қирра йўқ, яъни . Демак, бу ҳолда тасдиқ тўғридир.
Индуксион ўтиш: дарахт учун ва бўлганда 2) тасдиқ ўринли бўлсин деб фараз қиламиз. Энди учлари сони ва қирралари сони бўлган дарахтни қараймиз. Бу дарахтнинг ихтиёрий қиррасини билан белгилаб, ундан бу қиррани олиб ташласак, учдан учгача маршрути (аниқроғи, занжири) мавжуд бўлмаган графни ҳосил қиламиз, чунки агар ҳосил бўлган графда бундай занжир бор бўлса эди, у ҳолда дарахтда Цикл топилар эди. Бундай бўлиши эса мумкин эмас.
Ҳосил бўлган граф иккита ва боғламли компоненталардан иборат бўлиб, бу компоненталарнинг ҳар бири дарахтдир. Яна шуни ҳам эътиборга олиш керакки, ва дарахтларнинг ҳар биридаги учлар сони дан ошмайди.
Математик индуксия усулига кўра, бу дарахтларнинг ҳар бирида қирралар сони унинг учлари сонидан битта кам бўлишини таъкидлаймиз, яъни граф -граф бўлса, қуйидаги тенгликлар ўринлидир: , ва ( ). Бу тенгликлардан

бўлиши келиб чиқади. Демак, бўлганда ҳам тенглик ўринлидир. Бу эса, математик индуксия усулига кўра, керакли тасдиқнинг исботланганлигини англатади.
Енди дарахтлар ҳақидаги асосий теореманинг 2) тасдиғидан унинг 3) тасдиғи келиб чиқишини исботлаймиз. граф аЦиклик, яъни у Циклга эга бўлмаган граф ва бўлсин. графнинг боғламли бўлишини исботлаш керак.
Агар граф боғламли бўлмаса, у ҳолда уни ҳар бир боғламли компонентаси Циклсиз граф (яъни, дарахт) бўлган қандайдир та ( ) графлар дизъюнктив бирлашмаси сифатида тенглик билан ифодалаш мумкин. Ҳар бир учун граф дарахт бўлгани учун, юқорида исботлаган тасдиққа кўра, агар унда та уч ва та қирра бўлса, у ҳолда аЦикликдир ва тенглик ўринлидир. Тушунарлики, ва . Демак,
,
яъни граф учларининг умумий сони ундаги қирралар умумий сонидан та ортиқдир. Бу эса, бўлгани учун, тенгликка зиддир. Зарур тасдиқ исботланди.
Теореманинг 3) тасдиғидан унинг 4) тасдиғи келиб чиқишини исботлаймиз. – боғламли граф ва бўлсин. Аввало та боғламлилик компоненталарига эга каррали қирралари бўлмаган сиртмоқсиз -граф учун

муносабат ўринли бўлишини эслатамиз (ушбу бобнинг 4- параграфидаги 7- теоремага қаранг).
бўлгани сабабли боғламли графдан исталган қирра олиб ташланса, натижада та уч ва та қирралари бўлган граф ҳосил бўладики, бундай граф шартга биноан боғламли бўла олмайди. Керакли тасдиқ исботланди.
Дарахтлар ҳақидаги асосий теореманинг 4) тасдиғидан унинг 5) тасдиғи келиб чиқишини исботлаймиз. боғламли граф ва унинг ҳар бир қирраси кўприк бўлсин деб фараз қилиб, бу графниннг ўзаро устма-уст тушмайдиган исталган иккита учи фақат битта оддий занжир билан тутаҳтирилиши мумкинлигини кўрсатамиз. боғламли граф бўлгани учун, унинг исталган иккита учи ҳеч бўлмаса битта оддий занжир воситасида туташтирилади.
Агар қандайдир иккита уч биттадан кўп, масалан, иккита турли оддий занжир воситасида туташтирилиши имконияти бўлса, у ҳолда бу учларнинг биридан занжирларнинг бирортаси бўйлаб ҳаракатланиб иккинчи учга, кейин бу учдан иккинчи занжир бўйлаб ҳаракатланиб дастлабки учга қайтиш имконияти бор бўлар эди. Яъни қаралаётган графда Цикл топилар эди.
Табиийки, таркибида Цикл мавжуд бўлган графнинг Циклга тегишли исталган битта қиррасини олиб ташлаш унинг боғламлилиги хоссасини ўзгартирмайди, яъни бу ҳолда графнинг Циклга тегишли исталган қирраси кўприк бўлмайди. Бу эса қилинган фаразга зиддир. Теореманинг 4) тасдиғидан унинг 5) тасдиғи келиб чиқиши исботланди.
Енди теореманинг 5) тасдиғидан унинг 6) тасдиғи келиб чиқишини кўрсатамиз. Берилган графниннг ўзаро устма-уст тушмайдиган исталган иккита учи фақат битта оддий занжир билан туташтирилиши мумкин бўлсин. Тескарисини, яини граф аЦиклик эмас деб фараз қиламиз. Бу ҳолда, да Цикл топилади ва ундаги ихтиёрий Циклга тегишли исталган турли иккита учни камида иккита оддий занжир воситасида туташтириш имконияти бор. Бу эса графниннг ўзаро устма-уст тушмайдиган исталган иккита учи фақат битта оддий занжир билан туташтирилиши шартига зиддир.
графниннг қўшни бўлмаган ва учларини қирра билан туташтириш амалини қўллаш натижасида фақат битта Циклга эга бўлган граф ҳосил бўлишини кўрсатамиз. Шартга биноан қаралаётган ва учларни фақат битта оддий занжир билан тутаҳтириш мумкин. Оддий занжир таърифига кўра эса бу занжир таркибида Цикл йўқ. Шунинг учун ва учларни графниннг таркибида бўлмаган қирра билан туташтириш, албатта, таркибида Цикл топиладиган ва бу Цикл ягона бўлган графни ҳосил қилади. Теореманинг 5) тасдиғидан унинг 6) тасдиғи келиб чиқиши ҳам исботланди.
Ниҳоят, 1- теореманинг 6) тасдиғидаги шартлар бажа-рилса, графнинг дарахт бўлишини, яъни теореманинг 1) тасдиғи келиб чиқишини исботлаймиз. Фараз қилайлик, аЦиклик граф боғламли бўлмасин. У ҳолда, бу графнинг ихтиёрий боғламли компонентасидаги ихтиёрий учни унинг бошқа боғламли компонентасидаги ихтиёрий уч билан қирра воситасида туташтириш амалини қўллаш натижасида таркибида Цикл бўлган граф ҳосил бўлмайди. Бу эса 6) тасдиқнинг иккинчи қисмига зиддир. ■