299
правок
Изменения
→Индуцированная теорема Рамсея
==Индуцированная теорема Рамсея==
Докажем похожее на теорему Рамсея, но значительно более сложнее утверждение.
{{Определение
|id=def12
|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> называется рамсеееским графом для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>}}
При замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея. Для клики добавленное слово "индуцированный" ничего не меняет. Но значительно усложняет ситуацию для произвольного графа <tex>H</tex>.
{{Теорема
|id=th15.
|about=Индуцированная теорема Рамсея
|statement=Для любого графа существует рамсеевский граф
}}
===Случай двудольного графа===
===Случай произвольного графа===
