Здраствуйте! Помогите пожалуйста с доказательством теоремы. Никак не могу сообразить, что писать дальше. Тема про графы и их раскраску. Красим граф в два цвета, ибо больше не надо.
Формулировка: если граф имеет вид центральная вершина из которой выходит n (n>=3) лучей одинаковой длины (>=2) => раскраска не оптимальная.
Доказательство: Длина луча равна количеству закрашенных вершин при которых получаются две бесцветные вершины. Пусть это верно. Покажем, что при n = 3 выполняется это утверждение.
В общем тут еще надо как-то показать, что количество вершин в луче и количество самих лучей указывает на ту вершину, которая не будет вообще раскрашена. что -то вроде с увеличением количества лучей увеличивается количество бесцветных вершин. т.е. будет число бесцветных вершин = длине луча. а с графом, где число лучей равно 5 начинается, что число бесцветных вершин = количеству самих лучей. Интуитивно знаю, что это жуть как легко, но никак не соображу.