299
правок
Изменения
м
→Числа Рамсея для произвольных графов
1) Докажем, что <tex>r(T_n,K_m) \ge (m-1)(n-1)+1</tex>. Для этого предъявим раскраску рёбер графа K_{(m-1)(n-1)}, в которой нет ни одного связного подграфа на <tex>n</tex> вершинах с рёбрами цвета 1 и нет клики на <tex>m</tex> вершинах с рёбрами цвета 2. Разобьём вершины графа на <tex>m-1</tex> клику по <tex>n-1</tex> вершине и покрасим все рёбра этих клик в цвет 1. Тогда любой связный подграф с рёбрами цвета 1 содержит не более <tex>n-1</tex> вершины, в частности, нет подграфа с рёбрами цвета 1, изоморфного <tex>T_n</tex>. Рёбра цвета 2 (то есть, все оставшиеся рёбра) образуют <tex>(m-1)</tex>-дольный граф, в котором, очевидно, нет клики на <tex>m</tex> вершинах.
2) Рассмотрим произвольную раскраску рёбер полного графа <tex>K_{(m-1)(n-1)+1}</tex> в два цвета. Предположим, что не существует клики на <tex>m</tex> вершинах с рёбрами цвета 2. Тогда <tex>m>1</tex> и <tex>\alpha(G_1) \le m-1</tex>. По [[#lemma1l1|лемме1]], граф <tex>G_1</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах в частности, дерево, изоморфное <tex>T_n</tex>.
}}
