Граф

Пусть есть путь обхода графа, $A\rightarrow B\rightarrow \cdots \rightarrow C\rightarrow D$. Если он кратчайший, то $AB \leq AD$ и $CD \leq AD$. Десйтвительно, если, например, $AB > AD$, то легко показать, что длина пути $A\rightarrow B\rightarrow \cdots \rightarrow C\rightarrow D$ будет больше, чем длина пути $B\rightarrow C\rightarrow \cdots \rightarrow D\rightarrow A$, что не возможно, так как, по условию, первый путь кратчайший.