Задача
COM-B2-M04-P003 Конец самого длинного пути
#3
★★☆☆☆ Уровень 2 из 5
В конечном графе выбран путь максимальной длины \(v_1v_2\ldots v_k\). Докажите, что каждый сосед вершины \(v_k\) уже входит в этот путь.
Если есть сосед вне пути, что можно сделать с путём?
Предположим, что вершина \(v_k\) соединена с вершиной \(u\), которая не входит в путь. Тогда последовательность \(v_1v_2\ldots v_k u\) является путём и имеет на одну вершину больше.
Это противоречит выбору исходного пути как максимального по длине. Значит, все соседи \(v_k\) лежат на пути.
Это ключевая лемма для нескольких следующих задач.