теория-графов - Доказать, что в графе есть маршрут

Отметим, что речь может идти только о незамкнутом пути (полугамильтоновом маршруте). Понятно, что если из одной вершины всё только выходит (или если все стрелки в какую-то вершину только входят), то замкнутого пути с нужным свойством уже не будет.

Здесь всё доказывается по индукции. Для двух вершин утверждение очевидно. Пусть $%n > 2$%. Берём маршрут $%v_1\to v_2\to\cdots\to v_{n-1}$% в подграфе. Если из $%v_n$% можно пройти в $%v_1$%, то всё ясно. Также всё ясно, если из $%v_{n-1}$% можно пройти в $%v_n$%. Поэтому предположим, что стрелка идёт из $%v_1$% в $%v_n$%, и из $%v_n$% в $%v_{n-1}$%. Назовём вершину $%v_i$% ($%1\le i < n$%) красной, если из неё идёт стрелка в $%v_n$%, и назовём её синей, если стрелка идёт в обратном направлении. У нас первая вершина красная, а последняя синяя. Значит, имеется хотя бы один момент смены цвета -- когда $%v_i$% красная, а $%v_{i+1}$% синяя. Тогда искомый маршрут получается вставкой $%v_n$% между $%v_i$% и $%v_{i+1}$%.