Докажите, что в произвольном графе, в котором есть хотя бы одно ребро, можно раскрасить вершины в чёрный и белый цвета так, чтобы рёбер, концы которых покрашены в разные цвета, было больше, чем рёбер, концы которых покрашены в один цвет.
Ответы
Ответ:
Объяснение:
Докажем утверждение задачи индукцией по количеству вершин n. База. Пусть n=2, и вершины соединены ребром. Покрасим вершины в разные цвета, тогда утверждение будет выполнено.
Переход. Так как есть хотя бы одно ребро, и хотя бы 3 вершины, то можно удалить одну какую-то вершину A так, чтобы в оставшейся части графа осталось хотя бы одно ребро. По предположению индукции, оставшуюся часть графа можно раскрасить так, чтобы в ней количество разноцветных рёбер было больше количества одноцветных. Теперь посмотрим, с чем соединена вершина A. Если среди её соседей чёрных хотя бы столько, сколько белых, покрасим её в белый, иначе покрасим в чёрный. Получилось, что разноцветных рёбер из вершины A выходит хотя бы столько, сколько одноцветных. Таким образом, во всём графе разноцветных рёбер больше, чем одноцветных.