Тетрадка.бгИзбрани глави от комбинаториката и теория на графите.

Целта на нашия проект е да докажем, че при произволно черно-бяло оцветяване на граф с 9 върха съществува едноцветен (черен или бял) 5-цикъл. Под 5-цикъл разбираме свързан граф с 5 върха, чието обхождане започва от един връх, преминава през останалите 4 само по веднъж и последното ребро е свързано с първоначалния връх. Доказателството ни ще се извърши чрез допускане на противното, т.е. ще допуснем, че в граф с 9 върха не съществува едноцветен 5-цикъл. За да извършим доказателството, ще използваме твърдението, че R(C4, C4) = 6 наготово. Нека нашият граф има върхове 1, 2, 3, 4, 5, 6, 7, 8 и 9. От R(C4, C4) = 6, имаме, че в граф с 6 върха при черно-бяло оцветяване съществува едноцветен 4-цикъл, следователно и в нашия граф ще има такъв цикъл, т.к. той съдържа повече от 6 върха. Ще изберем този цикъл да бъде с върхове 1, 2, 3, 4 и да е бяло оцветен (т.е. върховете са свързани с бели ребра). Белите ребра са съответно (1, 2), (2,3), (3, 4), (4, 1) и полученият ни цикъл ще наричаме на кратко C4. За останалите 5 върха - 5, 6, 7, 8, 9 е възможно всеки от тях да е свързан с два несъседни върха на C4 с поне една двойка черни ребра. Нека например от 9 да излиза бяло ребро към 1. Ако (2, 9) е