Тетрадка.бгR(C5) и R(G2).

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