Yashiklar prinsipi

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