Yashiklar prinsipi

2- теорема (Ейлер 1752). Текис ва боғламли граф учун тенглик ўринлидир, бу ерда , , – ёқлар сони.
Исботи. Теоремани исботлаш учун математик индуксия усулини графдаги қирралар сони бўйича қўллаймиз. Индуксия усулининг базаси сифатида бўлган ҳолни қараймиз. Бу ҳолда теореманинг тасдиғига кўра бўлиши керак. Ҳақиқатдан ҳам, текис ва боғламли граф бўлгани учун, у ягона учдан ташкил топади ва бу уч ягона (чексиз) ёқда ётади, яъни ва . Демак, бу ҳолда теореманинг тасдиғи тўғридир.
Индуксион ўтиш: теореманинг тасдиғи учун тўғри бўлсин деб фараз қилиб, унинг учун ҳам тўғри эканлигини кўрсатамиз. Фаразимизга кўра тенглик ўринлидир. та қиррага эга текис ва боғламли графга ( )- қиррани (уни билан белгилаймиз) шундай қўшиш керакки, бунда қирра граф жойлашган текисликда ётсин ва ҳосил бўлган граф ҳам боғламли бўлсин. Бу амални бажарганда қуйидаги учта ҳолдан бири рўй беради:
1) қўшилаётган қирра сиртмоқдир – бу ҳолда қирра, албатта, графдаги учлардан бирига инсидент бўлиб, ёқлардан бирида ётади ва бу ёқни иккига (сиртмоқ ётган ёқнинг сиртмоқ чизиғи билан чегараланган ички ва ташқи қисмлари) ажратади, яъни учлар сони ўзгармайди, ёқлар сони эса бирга ошади: ;
2) қўшилаётган қирра графда бор бўлган иккита учларни туташтиради – бу ҳолда ҳам графнинг бирор ( қирра ётган) ёқи иккига ажралади, учлари сони эса ўзгармайди: ;
3) қўшилаётган қирра сиртмоқ эмас ва у графдаги учлардан фақат биттасига инсидентдир – бу ҳолда графнинг бирор ёқида қиррага инсидент бўлган битта бошқа уч ясалади (графнинг учлари сони биттага ошади) ва қирра жойлашган ёқ яхлитликни сақлаган ҳолда қиррани ўз ичига олади (ёқлар сони ўзгармайди): . ■
2- теореманинг тасдиғидаги тенглик эйлер формуласи деб аталади.
Ейлер формуласи стереометрияда ҳам қўлланилади: учлари та, ёқлари та ва қирралари та ихтиёрий кўпёқли учун эйлер формуласи ўринлидир. Бу тасдиқнинг негизида исботи ўқувчига ҳавола қилинаётган қуйидаги тасдиқ ётади: стереометрияда берилган таърифга кўра аниқланган ихтиёрий кўпёқлига мос текис изоморф граф мавжуддир.
Ейлер теоремасидан бир қатор натижалар келиб чиқади. Масалан, бу теоремадан фойдаланиб уни осонлик билан боғламли бўлмаган графлар учун қуйидагича умумлаштириш мумкин.