Но ведь можно поместить единицы в "центральную" вершину и одну из трех других, а в оставшиеся две - нули (?)
Это верно.
-- 06.04.2018, 21:13 --mihaild, отличный анализ! Значит то дерево из 6 вершин (смотрите выше, назовем его стулом) и является минимальным не счастливым деревом. Значит если существуют не счастливые графы с менее чем 6 вершинами то у них должен быть цикл.
-- 06.04.2018, 21:23 --Теперь допустим в минимальном не счастливом графе цикл из трех вершин (треугольник). Мы можем добавить одну или две вершины (до 5 вершин). Если новые вершины не соединены тогда граф можно осчастливить поставив 2 в треугольник и 0 в добавочные вершины, если они соединены тогда 2 в треугольник и 1 в добавочные вершины. Если же в минимальном не счастливом графе цикл из четырех вершин (и нет треугольника) тогда можно записать 2 в этот цикл и 0 в добавочную вершину. Если цикл из 5 вершин то везде ставим 2. Вроде других вариантов нет? В таком случае можно уверено сказать что минимальный не счастливый граф имеет 6 вершин.
