Yashiklar prinsipi

1- натижа. Текис граф учун тенглик ўринлидир, бунда , , – ёқлар сони, – боғламлилик компоненталар сони.
Исботи ўқувчига ҳавола қилинади ■.
2- натижа. Каррали қирралари бўлмаган сиртмоқсиз текис -граф учун тенгсизлик ўринлидир.
Исботи. Ҳақиқатдан ҳам, ҳар бир ёқ ҳеч бўлмақанда учта қирра билан чегараланганлиги ва ёқларни чегараловчи қирраларни санаганда ҳар бир қирра икки марта ҳисобда қатнашганлиги учун тенгсизлик ўринлидир (таъкидлаймизки, агар графда учта уч ва иккита қирра бўлса, у ҳолда тенгсизлик бажарилади). тенгсизликдан эйлер формуласини кўринишда қўллаб, тенгсизликни ҳосил қиламиз. ■
Ушбу бобнинг 2- параграфида ва графларнинг планар эмаслиги таъкидланган (исботсиз келтирилган) эди. Энди бу тасдиқларни қатъий исботлаш мумкин.
3- теорема. граф планар эмас.
Исботи. планар граф бўлсин деб фараз қиламиз. Планар граф учун тенгсизлик ўринлидир. граф учун ва бўлганлигидан бу тенгсизлик кўринишдаги нотўғри муносабатга олиб келади. Демак, граф планар эмас. ■
4- теорема. граф планар эмас.
Исботи. планар граф бўлсин деб фараз қиламиз. Бу графда 6та уч ( ) ва 9та қирра ( ) бўлгани учун, эйлер теоремасига кўра, унда 5та ( ) ёқ бўлиши керак. графнинг ҳар бир ёқи камида тўртта қирра билан чегараланганлиги сабабли бу граф учун тенгсизлик ўринлидир. Лекин бу тенгсизлик граф учун кўринишдаги нотўғри муносабатга олиб келади. Демак, граф планар эмас. ■
Исботлаш мумкинки, қуйидаги тасдиқ ўринлидир.
5- теорема. Агар бирор граф ёки графга гомеоморф бўлган қисм графга эга бўлса, у ҳолда бу граф текисликда ётувчи бўлмайди.
1930 йилда К. Куратовский бу тасдиққа тескари тасдиқни исбот қилди: агар граф текисликда ётувчи бўлмаса, у ҳолда у ёки графга гомеоморф бўлган қисм графга эга бўлади. Умуман олганда, графларнинг планарлиги ҳақидаги бу асосий натижа К. Куратовскийдан олдин 1922 йилда Л. С. Понтрягин томонидан исботланган, лекин бу натижа ўша вақтда матбуотда эълон қилинмаган эди.