Обоснование алгоритма Тэрри

Пусть в процессе работы мы остановились в некоторой вершине (не достигнув вершины ), и все ребра, инцидентные , уже пройдены, в направлении из (т.е. в силу правила 2 из этой вершины выйти уже невозможно). Покажем, что в этом случае:

а) вершина совпадает с ;

б) все вершины графа являются пройденными.

Доказательство утверждения «а»

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