6. В некотором графе все вершины раскрашены в 2 цвета. Каждую минуту одну из вершин, у которой больше половины соседей противоположного цвета, перекрашивают. Докажите, что процесс перекрашивания вершин не может продолжаться бесконечно.

Рассмотрим число одноцветных рёбер. Пусть у перекрашиваемой вершины \(r\) соседей того же цвета и \(s\) соседей противоположного цвета. По условию \(s>r\). После перекрашивания ровно рёбра, соединяющие эту вершину с соседями, меняют статус: одноцветных рёбер становится на \(s-r>0\) больше.

Число одноцветных рёбер — целое и не превышает общего числа рёбер графа. Оно строго увеличивается при каждом шаге, поэтому бесконечный процесс невозможен.

Ответ: процесс перекрашивания конечен.