Yashiklar prinsipi

3- теорема (Кели). Учлари сони бўлган белгиланган дарахтлар сони га тенг.
Исботи ўқувчига ҳавола қилинади.
3. Графнинг Цикломатик сони. Фараз қилайлик, сиртмоқсиз ва каррали қирралари бўлмаган қандайдир боғламли граф бўлсин. Бу гфафдан унинг бирор Циклига тегишли битта қиррасини олиб ташлаш натижасида ҳосил бўлган граф боғламли граф бўлиши равшандир. Графдан унинг бирор Циклига тегишли битта қиррасини олиб ташлаш амалини ҳосил бўлган графларга, имкони борича, кетма-кет қўллаш натижасида графнинг барча учларини боғловчи граф – дарахтни ҳосил қилиш мумкин. Бундай дарахт графнинг синч дарахти (синчи, каркаси, қобирғаси) деб аталади.
Табиийки, битта графнинг бир неча синч дарахтлари мавжуд бўлиши мумкин.
2- мисол. 3- шаклда тасвирланган граф синчларидан бирининг қирралари берилган графнинг бошқа қирраларига қараганда қалинроқ чизичлар воситасида ифодаланган. ■
Енди сиртмоқсиз ва каррали қирралари бўлмаган та уч, та қирра ва та боғламли компоненталардан ташкил топган граф бўлсин. Агар юқорида тавсифланган усул ёрдамида графдан қирраларни кетма-кет олиб ташлаш амалини қўллаш натижасида унинг ҳар бир компонентаси боғламлилиги бузилмаса, у ҳолда берилган графнинг синч ўрмони деб аталувчи графни ҳосил қилиш мумкин.
Берилган графдан унинг синч ўрмонини ҳосил қилиш мақсадида олиб ташланиши керак бўлган қирралар сони бу қирраларни олиб ташлаш тартибига боғлиқ эмаслиги ва бўлиши равшандир. Қаралаётган граф учун тенгсизлик ўринли бўлганлигидан, бўлади. сонни графнинг Цикломатик сони (Циклик ранги) деб атаймиз.
Графнинг Цикломатик сони тушунчаси, қандайдир маънода, графнинг боғламлилик даражасини аниқловчи воситадир. Равшанки, дарахт учун бўлади (1- теоремага қаранг).
Графнинг ўрмон бўлиши учун унинг Цикломатик сони нолга тенг бўлиши зарур ва етарлидир (2- натижага қаранг).
Графнинг ягона Циклга эга бўлиши учун унинг Цикломатик сони бирга тенг бўлиши зарур ва етарлидир. Қирралари сони учлари сонидан кичик бўлмаган граф Циклга эгадир. Бу тасдиқлар ҳам 1- теореманинг натижаларидир.