Докажем по индукции. База: $n=2$ — одна дуга, гамильтонов путь существует. Шаг: пусть утверждение верно для $n-1$ вершин. Добавим вершину $v$. По индукции в оставшихся $n-1$ вершинах есть гамильтонов путь $v_1, v_2$, ..., $v_{n-1}$. Если дуга $(v, v_1)$ существует, то $v, v_1$, ..., $v_{n-1}$ — гамильтонов путь. Если дуга $(v_{n-1}, v)$ — то $v_1$, ..., $v_{n-1}, v$. Иначе найдём наименьший $k$ такой, что $(v_k, v)$ — дуга, но $(v, v_{k+1})$ — дуга (такой $k$ существует). Тогда $v_1$, ..., $v_k, v, v_{k+1}$, ..., $v_{n-1}$ — гамильтонов путь.

💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!