<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>.
}}
==Индуцированная теорема число Рамсея==
{{Определение
|id=def9
|about=6, Индуцированная теорема Рамсея
|statement=Для любого графа существует рамсеевский граф
}}
===Случай двудольного графа===
Здесь мы будем рассматривать двудольный граф <tex>G</tex>, как <tex>G=(V_1(G),V_2(G),E(G))</tex>,
где <tex>V_1(G)</tex> и <tex>V_2(G)</tex> — разбиение множества вершин <tex>V(G)</tex> на две доли, а рёбра соединяют вершины из разных долей.
{{Определение
|id=def11
|definition=
Пусть <tex>H,G</tex> — двудольные графы. Инъективное отображение <tex>\phi:V(H)\rightarrow V(G)</tex> назовём '''погружением''' (англ. ''immersion''), если оно удовлетворяет двум условиям.<br>
<tex>1)</tex><tex>\phi(V_1(H)) \subset V_1(G), \phi(V_2(H)) \subset v_2(G)</tex><br>
<tex>2)</tex><tex>\phi(u)\phi(v) \in E(G)</tex> тогда и только тогда когда <tex>uv\in E(H)</tex>
Будем говорить, что двудольный граф <tex>H</tex> погружён в двудольный граф <tex>G</tex> и использовать обозначение <tex>\phi(H)=G(\phi(V(H)))</tex>
}}
{{Лемма
|id=l2|about=2
|statement=Любой двудольный граф может быть погружен в особый двудольный граф.
|proof=
Рассмотрим произвольный двудольный граф <tex>P</tex>, пусть <tex>V_1(P)=\{a_1,...,a_n\}, V_2(P)=\{b_1,...,b_n\}</tex>. Положим
<tex>V=\{x_1,...,x_n,y_1,...,y_n,z_1,...,z_m\}</tex>
Построим погружение <tex>P</tex> в особый двудольный граф <tex>H=(V,V^{n+1},E)</tex>.
Изначально положим <tex>\phi(a_i)=x_i</tex>. Попробуем построить такое множество <tex>Y_j\in V^{n+1}</tex>, что <tex>\phi(b_j)=Y_j</tex>. По определению погружения и множества <tex>E(H)</tex>, должно выполняться условие:<br>
<tex>Y_j\cap\{x_1,...,x_n\}=\phi(N_P(b_j)</tex>
Условие оставляет незаполненными <tex>n+1-d_P(b_j)\ge 1</tex> элементов множества <tex>Y_j</tex> (единственное ограничение эти элементы не могут быть вершинами <tex>x_1,...,x_n</tex>). Поместим в <tex>Y_j</tex> элемент-индекс <tex>z_j</tex> (чтобы <tex>Y_j\not=Y_l</tex> при <tex>j \not=l</tex>, и дополним произвольно элементами из <tex>y_1,...,y_n</tex>, чтобы в множестве <tex>Y_j</tex> было ровно <tex>n+1</tex> элементов.
}}
{{Лемма
|id=l3|about=3
|statement=Для любого двудольного графа <tex>H</tex> существует такой двудольный граф <tex>G</tex>, что для любой раскраски рёбер <tex>G</tex> в два цвета обязательно существует погружение <tex>\phi</tex> графа <tex>H</tex> в граф <tex>G</tex> в котором все рёбра <tex>\phi(H)</tex> одноцветны.
|proof=Разумеется, указанный в условии [[#l3|леммы <tex>3</tex>]] граф <tex>G</tex> будет рамсеевским графом для <tex>H</tex>. Утверждение леммы более сильное: мы дополнительно требуем, чтобы все вершины одной доли <tex>H</tex> можно было погрузить в одну долю графа <tex>G</tex>.
Ввиду [[#l2|леммы <tex>2</tex>]] достаточно доказать утверждение для особого двудольного графа <tex>H=(V,V^k,E(H))</tex>. Пусть <tex>|V|=n</tex>. Докажем что рамсеевским графом для <tex>H</tex> будет особый двудольный граф <tex>G=(U,U^{2k-1},E(G))</tex>, где
<tex>|U|=r_{2k-1}(2C^k_{2k-1};kn+k-1,...,kn+k-1).</tex> <tex>(**)</tex>
Рассмотрим произвольную раскраску рёбер графа <tex>G</tex> в два цвета 1 и 2. Каждое множество <tex>Y\in U^{2k-1}</tex> смежно как вершина особого двудольного графа <tex>G</tex> с <tex>2k-1</tex> вершиной, хотя бы <tex>k</tex> из этих рёбер имеет одинаковый цвет. Выберем и зафиксируем для каждого множества <tex>Y</tex> его подмножество <tex>S(Y)</tex>, состоящее из <tex>k</tex> вершин доли <tex>U</tex> соединённых с <tex>Y</tex> рёбрами одинакового цвета. Пусть <tex>c(Y)\in \{1,2\}</tex> — это цвет рёбер соединяющий <tex>Y</tex> с вершинами из <tex>S(Y)</tex>.
Можно считать, что элементы <tex>U</tex> упорядочены. Тогда элементы каждого множества <tex>Y\in U^{2k-1}</tex> будут упорядочены. Обозначим через <tex>\sigma(Y)</tex> множество номеров <tex>k</tex> элементов множества <tex>S(Y)</tex> в порядке элементов множества <tex>Y</tex>. Тогда <tex>\sigma(Y)</tex> может принимать ровно <tex>C^k_{2k-1}</tex> значений.
Покрасим множество <tex>U^{2k-1}</tex> (то есть все <tex>(2k-1)</tex>-элементные подмножества <tex>U</tex>) в <tex>2C^k_{2k-1}</tex>цветов: цветом подмножества <tex>Y</tex> будет пара <tex>(\sigma(Y),c(Y))</tex>. Из выбора размера множества <tex>U</tex> (из условия <tex>(**)</tex>) следует, что ceotcndetn такое подмножество <tex>W\subset U</tex>, что <tex>|W|=kn+k-1</tex> и все подмножества <tex>Y\subset W^{2k-1}</tex> имеют одинаковый цвет <tex>(\sigma(Y),c(Y))</tex> (не умаляя общности будем считать, что <tex>\sigma(Y)=\sigma, c(Y)=1)</tex>. Мы найдём погружение графа <tex>H</tex> в <tex>G(W)</tex>, все рёбра в котором покрашены в исходной раскраске в цвет 1 и тем самым докажем лемму.
Занумеруем элементы множества <tex>W</tex> в порядке их следования в <tex>U</tex>: пусть <tex>W=\{w_1,...,w_{kn+k-1}\}</tex>. Введем обозначения
<tex>t_j=w_kj, T=\{t_1,...,t_n\}, V=\{a_1,...,a_n\}</tex>.
Положим <tex>\phi(a_i)=t_i</tex>. Остаётся корректно определить <tex>\phi(Z)</tex> для каждого множества <tex>Z\in V^k</tex>. Прежде чем построить <tex>\phi(Z)=Y\in U^{2k-1}</tex> мы положим <tex>S(Y)=\{\phi(x):x\in Z\}</tex>. Из определения погружения понятно, что тогда должно выполняться условие <tex>S(Y)=Y\cap T</tex>, а следовательно, нам нужно дополнить множество <tex>Y</tex> еще <tex>k-1</tex> элементами, не входящими в множество <tex>T</tex>. Мы сделаем это так, чтобы множество порядков номеров элементов множества <tex>S(Y)</tex> среди элементов множества <tex>Y</tex> было <tex>\sigma(Y)=\sigma</tex>: так как <tex>t_i=w_ki</tex>, не входящих в <tex>T</tex> элементов <tex>W</tex> хватит, чтобы обеспечить это.
Так как по выбору множества <tex>W</tex> мы имеем <tex>\sigma(Y)=\sigma</tex>, множество <tex>S(Y)</tex> выбрано корректно и, опять же в силу выбора <tex>W</tex>, все рёбра особого двудольного графа <tex>G</tex> между вершинами из <tex>S(Y)=\{\phi(x):x\in Z\}</tex> и <tex>Y=\phi(Z)</tex> покрашены в цвет 1. В завершение остается лишь добавить, что при <tex>Z\not=Z'</tex> мы по построению имеем <tex>S(\phi(Z))\not=S(\phi(Z'))</tex>, поэтому <tex>\phi(Z)\not=\phi(Z')</tex>. Таким образом искомое погружение построено.
}}
