Граф G можно по крайней мере тремя различными способами правильно раскрасить в 2 цвета. Докажите, что G несвязный.

Предположим, что граф G связен. Так как по условию его можно покрасить в 2 цвета, то в нем нет
циклов нечетной длины, то есть граф двудольный. Пусть он разбивается на доли A и B.
Заметим, что в таком графе есть только два различных способа правильно раскрасить вершины в 2
цвета: вершины доли A белые, вершины доли B черные, и наоборот. Но по условию граф G можно
раскрасить в два цвета хотя бы 3-мя способами – противоречие. Тогда граф G не связен.


info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp