Это следует из правила проведения обхода в глубину.
Если предположить противное, то существует вершина

, что она соединена ребром с родителем

и ребром с некоторым своим другим предком

, который является также и предком

, причём оба эти ребра лежат в дереве обхода. Вопрос: как могло получиться, что в вершину

в ходе алгоритма мы попали из

, если есть ребро

?