Yashiklar prinsipi

3- натижа. та учга эга, қирралари сони дан катта, каррали қирралари бўлмаган сиртмоқсиз граф боғламлидир.
Исботи. Биринчидан, агар сиртмоқсиз ва каррали қирралари бўлмаган графнинг боғламлилик компоненталари сони га тенг бўлса ( ), у ҳолда, 7- теоремага биноан, бундай графнинг қирралари сони дан катта эмас. Иккинчидан, тенгсизлик фақат бўлсагина тўғридир. ■
Табиийки, боғламли графдан қиррани ёки бир неча қирраларни олиб ташлаш натижасида ҳосил бўлган граф боғламли бўлиши ҳам бўлмаслиги ҳам мумкин. Агар боғламли графдан қиррани олиб ташлаш амали графнинг боғламлилик хусусиятини бузса, у ҳолда бундай қиррани ажратувчи қирра деб атаймиз.
Равшанки, берилган боғламли графда ажратувчи қирралар кўп бўлишлари мумкин. Ажратувчи қирралар тўпламининг ҳеч қайси қисм тўплами элементлари ажратувчи қирралар бўлмаса, бу қирралар тўпламини кесим деб атаймиз. Графдан кесимга тегишли қирралар олиб ташланса, натижада икки боғламли компоненталари бўлган граф ҳосил бўлиши равшандир. Агар кесим ягона қиррадан иборат бўлса, у ҳолда бу қирра кўприк деб аталади.
3
- мисол. 1- шаклда тасвирланган (15,14)-графни билан белгилаймиз.
Бу граф боғламли граф эмас, унинг тўртта боғламли компоненталари бор: , бу ерда – учлари тўплами бўлган ориентирланмаган (6,7)-граф, – битта 7 белгили учга эга ориентирланмаган (1,0)-граф, ҳам битта 10 белгили учга эга ориентирланмаган (1,0)-граф, эса учлари тўплами бўлган ориентирланмаган (7,7)-графдир. Агар графнинг боғламли компонентасини алоҳида граф деб қарасак, бу графда кўринишдаги ажратувчи қирралар тўпламини кўрсатиш мумкин. Бу қирралар кесим ташкил этади. графнинг ва боғламли компоненталари кўприкларга эгадир. Масалан, ва қирралар граф учун кўприклардир. ■
Енди Д. Кёниг томонидан 1936 йилда исботланган ушбу теоремани графнинг икки бўлакли бўлиши ёки бўлмаслигини текшириш аломати (мезони) сифатида келтирамиз.