Yashiklar prinsipi

1- теорема. Ҳар қандай чекли графни 3 ўлчовли эвклид фазосида геометрик ифодалаш мумкин.
Исботи. Теореманинг қуйидаги конструктив исботини келтирамиз. Графнинг абстракт таърифига биноан унинг ҳеч бўлмаса битта учи мавжуд. Агар графда фақат битта уч бўлса, у ҳолда уни 3 ўлчовли эвклид фазосининг бирор нуқтаси сифатида ифодалаймиз. Агар графда учлар биттадан кўп бўлса, у ҳолда уларни уч ўлчовли эвклид фазосидаги бирор тўғри чизиқнинг (ҳеч қайси иккитаси устма-уст тушмайдиган) нуқталарига мос келади деб ҳисоблаймиз. Шу тўғри чизиқдан қирраларнинг (ёйларнинг) ҳар бирига мос келувчи турли ярим текисликларни ўтказамиз (граф чекли бўлгани учун бунинг имконияти бор). Ҳар бир қиррани (ёйни) унга мос ярим текисликда, четлари мос учларни ифодаловчи нуқталарда бўлган ҳамда бу тўғри чизиқ билан бошқа умумий нуқтаси бўлмаган қандайдир чизиқ воситасида ифодалаймиз. Ярим текисликларнинг тузилишига кўра бу чизиқлар, четки нуқталарни ҳисобга олмаганда, умумий нуқталарга эга эмас. ■
Шуни ҳам таъкидлаш керакки, 1- теоремадаги 3ни 2га алмаштириб бўлмайди, чунки текисликда қирраларини (ёйларини) ифодаловчи кесишмайдиган (аниқроғи, четки нуқталаридан бошқа умумий нуқталари бўлмаган) чизиқлар ёрдамида тасвирлаш имконияти фақат баъзи графларгагина хос, яъни ҳар қандай графнинг 2 ўлчовли эвклид фазосида (текисликда) геометрик ифодаланиши мавжуд бўлавермайди.
Графларнинг геометрик ифодаланишига доир мисоллар келтирамиз.
1- мисол. 1- шаклда тасвирланган графни деб белгилаймиз. Берилган граф белгиланган граф бўлиб, 4та уч ва 6та қиррага эга. Демак, у (4,6)-графдир. Бу граф учун: , , , , , , . графнинг барча ( ) қирралари ориентирланмаган (чунки учларини туташтирувчи чизикларда йўналиш кўрсатилмаган) бўлгани учун ориентирланмаган графдир. Графнинг қирраларидан бири, аниқроғи, сиртмоқдир, ва эса каррали қирралардир. Бу графда, масалан, 1 ва 2 учлар қўшни, 1 ва 4 учлар эса қўшни эмас. Ундаги 2 ва 3 учлар қиррага инсидент ва, аксинча, қирра 2 ва 3 учларга инсидентдир. Бу ерда ва қирралар қўшни қирралардир, чунки улар умумий учга (3 уч) эга, ва қирралар эса қўшни эмас. ■
2- мисол. Геометрик ифодаланиши 2- шаклдаги кўринишда бўлган ориентирланган графни қараймиз. Бу графда ўн битта элемент бор: 5та уч ва 6та ёй, яъни шаклда (5,6)-орграф берилган. Бу графни билан белгилаймиз, бу ерда , ёки . Берилган орграфда сиртмоқ ҳам, каррали ёйлар ҳам йўқ. Бу графнинг ёйи учун 1 бошланғич, 3 уч эса охирги учдир. ■

4- мисол. 3- шаклда тасвирланган графлар бир-бирига изоморфдир. ■