Yashiklar prinsipi

2. Графнинг махсус турдаги кўпҳад ёрдамида берилиши.
Графни махсус турдаги кўпҳад ёрдамида ҳам бериш мумкинлигини таъкидлаймиз. Учлари тўплами бўлган граф берилган бўлсин. графнинг яккаланган учлари йўқ деб фараз қиламиз,. Бу графни та ўзгарувчиларга боғлиқ

кўринишдаги кўпҳад ёрдамида тасвирлаш мумкин, бу ерда кўпайтма шартни қаноатлантирувчи барча жуфтлар бўйича амалга оширилади, ўзгарувчи учга мос келади, – ва учларни туташтирувчи қирралар сони, – учдаги сиртмоқлар сони.
кўпҳад графга изоморфлик аниқлигида мос келишини исботлаш мумкин.
6- мисол. 9- шаклда тасвирланган графга мос кўпҳадни аниқлаймиз. Берилган ориентирланмаган графда еттита уч ва саккизта қирра бор. Унинг ҳар бир учига битта ( ) ўзгарувчини мос қ1илиб қўямиз. графда каррали қирралари йўқ, унинг учта қирраси сиртмоқ-лардан иборат бўлиб, улардан иккитаси 3 учга, бири эса 5 учга инсидентдир. Шунинг учун , , ; , қолган барча бўлади. Берилган графга мос кўпҳад

кўринишга эга бўлади. ■
7- мисол. кўпҳадга мос келувчи графнинг геометрик тасвирини топамиз. Бу кўпҳаднинг таркибига кўра унга мос келувчи ориентирланмаган графда 4та уч ва 6та қирра бўлиб, бу қирралардан иккитаси каррали ( ) ва биттаси сиртмоқ ( ) эканлигини таъкидлаймиз. Берилган графнинг геометрик тасвирланишларидан бири 1- шаклда келтирилган. ■
3. Қўшнилик матритсалари.
Энди графнинг бошқа бир берилиш усули негизида ётувчи граф учлари қўшнилиги матритсаси тушунчасини қараб чиқамиз.
– учлари сони га тенг бўлган белгиланган, сиртмоқсиз ва каррали қирраларсиз граф бўлсин.
Елементлари

кўринишда аниқланган ( ; ) матритсани графнинг учлари қўшнилиги матритсаси деб атаймиз.
Бу таърифдан сиртмоқсиз ва каррали қирралари бўлмаган граф учлари қўшнилиги матритсасининг бош диагоналида фақат ноллар бўлиши, сатрларидаги бирлар сони эса мос учларнинг даражаларига тенглиги келиб чиқади.