Тетрадка.бгКурсова работа на тема Теореми на Рамзи.

При всяко 2-оцветяване на ребрата на К в черен и бял цвят със сигурност има черен или бял триъгълник и това не е вярно за К . Сега ще докажем следната Теорема 1 ( Грийнууд и Глисън ). При всяко 2-оцветяване на ребрата на К в черен и бял цвят сигурно има черен триъгълник или бял тетраедър. За К такова твърдение не е в сила. За доказателството на теоремата ще използваме Лема 1. Ако съществува 2-оцветяване на ребрата на К , при което няма нито черен триъгълник, нито бял тетраедър, тогава при такова оцветяване от всеки връх излизат най-много 3 черни и 5 бели ребра. Доказателство. Допускаме, че [v, v ],[v, v ],[v, v ] и [v, v ] са черни ребра, тогава никои два от върховете v не са съединени с черно ребро, понеже няма черен триъгълник. От тук следва, че [v , v , v , v ] е бял тетраедър, с което получаваме противоречие. А сега да допуснем, че [v, v ], i = 1, 2…, 6, са бели ребра. Разглеждаме подграфа К6, породен от върховете v , v ,…,v . В К няма черни триъгълници, следователно и в К няма черни тръгълници. Тогава в К има поне един бял триъгълник. Заедно с върха v той образува бял тетраедър, което отново е противоречие. Лема 1 е доказана. Теорема 1 се разлага на две т