Изменения

Таким образом, существует изоморфный <tex>G^0</tex> индуцированный под­граф графа <tex>G</tex>, в котором для каждой пары строк <tex>i,j</tex> все ребра между вершинами соответствующих строк одноцветны в раскраске <tex>\rho</tex>. Будем обозначать этот граф просто <tex>G^0</tex>. Рассмотрим граф <tex>K_n</tex>, вершины которого соответствуют строкам таблицы и покрасим каждое ребро в цвет, в который покрашены рёбра <tex>G^0</tex> между соответствующими строками. Так как <tex>n=r(k,k)</tex>, существуют <tex>k</tex> вершин, между которыми все рёбра одноцветны. Рассмотрим столбец графа <tex>G^0</tex>, в котором <tex>H</tex> размещён именно в строчках, соответствующих этим <tex>k</tex> вершинам. Подграф <tex>H'</tex> графа <tex>G^0</tex> на вершинах этого столбца и соответствующих строчках изоморфен <tex>H</tex>, по построению является индуцированным подграфом графа <tex>G^0</tex> и все его рёбра одноцветны в раскраске <tex>\rho</tex>. Остаётся лишь заметить, что <tex>H'</tex> — индуцированный подграф графа <tex>G</tex>.

}}

==См. также==

*[[Раскраска графа]]

*[[Раскраска двудольного графа в два цвета]]

*[[Теорема Турана об экстремальном графе]]

== Источники информации ==