Изменения

|id=lemma1 |statement=Пусть <tex>m>1</tex>, а граф <tex>H</tex> таков, что <tex>v(H) \ge (m-1)(n-1)+1</tex> и <tex>\alpha(H) \le m-1</tex>. Тогда граф <tex>H</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах.

|proof=доказательство (необязательно)Доказательство, 1] ) Докажем, что <tex>r(TnT_n, КтK_m) > \ge (т — m-1)(п — n-1) + 1</tex>. Дляэтего нредъяЕим этого предъявим раскраску рёбер графа ^K_{(т.m-1)(тгn-1) е ксторей }, в которой нет ни одного СЕязногс связного подграфа на п Еершинах <tex>n</tex> вершинах с рёбрами цвета 1 и нет клики на т <tex>m</tex> вершинах с рёбрами цвета 2. Разсбьём Есршнны Разобьём вершины графа ш т—1 на <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> вершинах. 12) Рассмотрим нроизЕСльную произвольную раскраску рёбер полного графа K<tex>K_{(m-i1)(n-i1)+i 1}</tex> в два цвета. Предположим, что не сушестьует клнки существует клики на то <tex>m</tex> вершинах с рёбрами цвета 2. Тсгда то Тогда <tex>m> 1 </tex> и a<tex>\alpha(GiG_1) \le m-1< m—1/tex>. По [[#lemma1|лемме 10 1]], граф Gi <tex>G_1</tex> содержит е в качестве подграфа любее любое дерево на п <tex>n</tex> вершинах в частности, дереведерево, иземерфнее Тпизоморфное <tex>T_n</tex>. □