442
правки
Изменения
Нет описания правки
<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
|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> называется рамсеееским графом для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>}}
При замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея.
{{Теорема
|id=ter6
|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=def10
|definition=
Пусть <tex>H,G</tex> — двудольные графы. Инъективное отображение <tex>\phi:V(H)\rightarrow V(G)</tex> назовём погружением, если оно удовлетворяет двум условиям.<br>
1)<tex>\phi(V_1(H)) \subset V_1(G), \phi(V_2(H)) \subset v_2(G)</tex><br>
2)<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>
}}
==См. также==
