442
правки
Изменения
→Существование. Оценки сверху
Пусть <tex>|M|\geqslant r(n-1,\;m)</tex>. Тогда либо в <tex>M</tex> (и следовательно во всём графе) есть белый <tex>K_m</tex>, что завершает доказательство, либо в <tex>M</tex> есть чёрный <tex>K_{n-1}</tex>, который вместе с <tex>v</tex> образует чёрный <tex>K_n</tex>. Случай <tex>|N|\geqslant r(n,\;m-1)</tex> рассматривается аналогично.
<tex>2)</tex> Предположим, <tex>p=Rr(rn-1,\;sm)</tex> и <tex>q=Rr(rn,\;sm-1)</tex> оба чётны. Положим <tex>t=p+q-1</tex> и рассмотрим чёрно-белый граф из <tex>t</tex> вершин. Если <tex>d_i</tex> степень <tex>i</tex>-й вершины в чёрном подграфе, то, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]], <tex>\sum_{i=1}^t d_i</tex> — чётно. Поскольку <tex>t</tex> нечётно, должно существовать чётное <tex>d_i</tex>. Для определённости положим, что <tex>d_1</tex> чётно. Обозначим через <tex>M</tex> и <tex>N</tex> вершины инцидентные вершине 1 в чёрном и белом подграфах соответственно. Тогда <tex>|M|=d_1</tex> и <tex>|N|=t-1-d_1</tex> оба чётны. Согласно [[Принцип Дирихле (комбинаторика)|принципу Дирихле (комбинаторика)]], либо <tex>|M|\geqslant p-1</tex>, либо <tex>N\geqslant q</tex>. Так как <tex>|M|</tex> чётно, а <tex>p-1</tex> нечётно, первое неравенство можно усилить, так что либо <tex>|M|\geqslant p</tex>, либо <tex>|N|\geqslant q</tex>.
Предположим <tex>|M|\geqslant p=Rr(rn-1,\;sm)</tex>. Тогда либо подграф, порождённый множеством <tex>M</tex>, содержит белый <tex>K_s</tex> и доказательство завершено, либо он содержит чёрный <tex>K_{rn-1}</tex>, который вместе с вершиной 1 образует чёрный <tex>K_rK_n</tex>. Случай <tex>|N|\geqslant q=Rr(rn,\;sm-1)</tex> рассматривается аналогично.
}}
{{Утверждение|id=u1|about=1|statement=Для натуральных чисел <tex>m,n</tex> выполняется равенство <tex>r(n,m) \le C_{n+m-2}^{n-1}</tex>
