Изменения

Перейти к: навигация, поиск

Теория Рамсея

41 байт убрано, 17:49, 30 ноября 2018
Особенности теории
<tex>2)</tex> Рассмотрим произвольную раскраску рёбер полного графа <tex>K_{(m-1)(n-1)+1}</tex> в два цвета. Предположим, что не существует клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2</tex>. Тогда <tex>m>1</tex> и <tex>\alpha(G_1) \le m-1</tex>. По [[#l1|лемме <tex>1</tex>]], граф <tex>G_1</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах, в частности, дерево, изоморфное <tex>T_n</tex>.
}}
==Особенности теории==
 
==См. также==
*[[Раскраска графа]]
442
правки

Навигация