Изменения

Так как <tex>\ k = degU </tex>, то вершина <tex>\ U </tex> может быть смежна, самое большее, с <tex>\ k </tex> из этих <tex>\ k+1 </tex> вершин. Значит существует вершина <tex>\ W </tex>, несмежная с <tex>\ U </tex>, и для которой <tex>\ degW \ge n-k </tex>. Но тогда получим <tex>\ degU + degW \ge k + (n - k) = n > degU + degV </tex>, что противоречит выбору <tex>\ U </tex> и <tex>\ V </tex>. <br>

}}