Yashiklar prinsipi

1- теорема. Агар графдаги ҳар бир учнинг локал даражаси иккидан кичик бўлмаса, у ҳолда бу граф сиклга эга.
Исботи. Агар графда сиртмоқлар ёки каррали қирралар бўлса, теореманинг тасдиғи тўғрилиги равшандир. Шунинг учун теорема тасдиғини граф сиртмоқсиз ва каррали қирралари бўлмаган ҳолда исботлаймиз.
Фараз қилайлик, берилган сиртмоқсиз ва каррали қирралари бўлмаган графнинг ихтиёрий учи бўлсин. Қаралаётган учга қўшни учни ва бу учга дан фарқли бошқа қўшни учни, учга эса дан фарқли бошқа қўшни учни, ва ҳакоза, учга дан фарқли бошқа қўшни учни, ва ҳакоза, танлаб,

қирралар кетма-кетлигини тузамиз. Теореманинг шартларига кўра юқоридаги жараённи амалга ошириш ва талаб этилган хоссага эга учни топиш мумкинлигини таъкидлаймиз.
Графнинг учлари тўплами чекли тўплам бўлганлигидан, юқорида баён этилган учлар кетма-кетлигини қуриш жараёнида чекли қадамдан сўнг албатта олдин учраган учлардан бирини танлашга мажбур бўламиз. Агар уч кетма-кетликда икки марта учраган дастлабки уч бўлса, кетма-кетликка қирралар қўшиш жараёнини тўхтатамиз, чунки тузилган қирралар кетма-кетлигининг уч икки марта қатнашган қисми биз излаётган сиклдир. ■
2. Графнинг боғламлилиги тушунчаси.
Агар ориентирланмаган графда четлари ва учлардан иборат маршрут топилса, бу ва учлар боғланган деб, маршрутнинг ўзи эса ва учларни боғловчи маршрут дебаталади.
Табиийки, агар қандайдир учларни боғловчи маршрут бирор учдан бир неча марта ўтса, у ҳолда маршрутнинг сиклик қисмини олиб ташлаб (бунда сиклик қисмнинг ўрнига маршрутда фақат уч қолдирилади) яна ўша учларни боғловчи оддий занжир кўринишдаги маршрутни ҳосил қилиш мумкин. Шунинг учун, маршрут билан боғланган учлар доимо оддий занжир билан ҳам бўгланган бўлади деган хулосага келамиз.
Бир-бири билан устма-уст тушмайдиган ихтиёрий иккита учлари боғланган граф боғламли граф деб аталади.
Агар графдаги иккита учни бирор оддий занжир билан туташтириш мумкин бўлса, у ҳолда бу иккита уч эквивалент (боғланган) дейилади. Бундай учлар тўплами графда эквивалентлик муносабати билан аниқланган деб ҳисобланади. Учлар тўплами бўйича эквивалентлик муносабатини инобатга олган ҳолда берилган графни боғламлилик компоненталари (қисқача, компоненталари) деб аталувчи боғламли қисмларнинг бирлашмаси деб қараш мумкин. Бу ерда берилган граф боғламлилик компоненталарига бўлакланди (ажратилди) деб айтиш мумкин. Исботлаш мумкинки, ҳар қандай граф ўзининг боғламлилик компоненталарининг дизъюнктив бирлашмаси сифатида ифодаланиши мумкин, бунда графнинг боғламлилик компоненталарига бўлакланиши бир қийматли аниқланади.
Кейинги маълумотларни баён этиш учун ёқ тушунчаси зарур бўлади. Текисликда геометрик ифодаланувчи графни қараймиз. Бу графга тегишли бўлмаган (яъни графнинг ҳеч қайси учи билан устма-уст тушмайдиган ва унинг ҳеч қайси қиррасида ётмайдиган) бирор нуқтани ҳеч қайси нуқтаси графга тегишли бўлмаган узлуксиз чизиқ билан туташтириш мумкин бўлган барча нуқталар тўплами графнинг нуқтани ўзида сақловчи ёқи деб аталади.
Ёқ тушунчасига берилган таърифга кўра ёқ графнинг геометрик ифодаланиши ёрдамида текисликнинг “қирқиб” олинадиган қисмидан иборатдир. Текисликда геометрик ифодаланувчи ихтиёрий графнинг ҳеч бўлмаганда битта ёқи бўлиши ва унинг битта ёқи чегарага эга эмаслиги (чексизлиги) ўз-ўзидан равшандир.