Yashiklar prinsipi

Маршрутнинг узунлиги деб ундаги қирралар сонига айтилади.
Турли қирралардан ташкил топган маршрутга занжир деб аталади. Агар занжирнинг четларидан ташқари барча учлари турлича бўлса, у ҳолда уни оддий занжир деб атайдилар.
Берилган занжир ёки оддий занжир учун бўлса, у ёпиқ занжир деб аталади. Ҳеч бўлмаганда битта қиррага эга ёпиқ оддий занжир сикл деб аталади.
Сиртмоқ ёки бир жуфт каррали қирралар сикл ташкил этиши равшандир.
Тушунарлики, графдаги занжир графнинг қисм графи деб қаралиши мумкин.
Ориентирланган графлар учун ҳам ундаги ёйларнинг йўналишини (ориентатсиясини) инобатга олмасдан ориентирланмаган маршрут, занжир ва оддий занжир тушунчаларини киритиш мумкин. Лекин, ориентирланган графлар учун ориентирланган маршрут тушунчасини киритиш табиийдир.
Ёйларнинг ориентатсиялари ҳисобга олинган ёйлар ва учлар кетма-кетлиги ориентирланган маршрут деб аталади.
Ориентирланган маршрут учун занжир тушунчасига ўхшаш йўл (ёки ориентирланган занжир) тушунчасини ҳам киритиш мумкин. Бошланғич ва охирги учлари устма-уст тушадиган ориентирланган занжир контур деб аталади.
1- теорема. Агар графдаги ҳар бир учнинг локал даражаси иккидан кичик бўлмаса, у ҳолда бу граф сиклга эга.
Исботи. Агар графда сиртмоқлар ёки каррали қирралар бўлса, теореманинг тасдиғи тўғрилиги равшандир. Шунинг учун теорема тасдиғини граф сиртмоқсиз ва каррали қирралари бўлмаган ҳолда исботлаймиз.
Фараз қилайлик, берилган сиртмоқсиз ва каррали қирралари бўлмаган графнинг ихтиёрий учи бўлсин. Қаралаётган учга қўшни учни ва бу учга дан фарқли бошқа қўшни учни, учга эса дан фарқли бошқа қўшни учни, ва ҳакоза, учга дан фарқли бошқа қўшни учни, ва ҳакоза, танлаб,

қирралар кетма-кетлигини тузамиз. Теореманинг шартларига кўра юқоридаги жараённи амалга ошириш ва талаб этилган хоссага эга учни топиш мумкинлигини таъкидлаймиз.
Графнинг учлари тўплами чекли тўплам бўлганлигидан, юқорида баён этилган учлар кетма-кетлигини қуриш жараёнида чекли қадамдан сўнг албатта олдин учраган учлардан бирини танлашга мажбур бўламиз. Агар уч кетма-кетликда икки марта учраган дастлабки уч бўлса, кетма-кетликка қирралар қўшиш жараёнини тўхтатамиз, чунки тузилган қирралар кетма-кетлигининг уч икки марта қатнашган қисми биз излаётган сиклдир. ■