Изменения

Пусть дан граф <tex>G</tex>. Запустим <tex>dfs(G)</tex>. Рассмотрим выполнение процедуры поиска в глубину от некоторой вершины <tex> v </tex>. Так как все серые вершины лежат в стеке рекурсии, то для них вершина <tex> v </tex> достижима по [[Лемма о белых путях|белым путям]]. Тогда если из рассматриваемой вершины <tex> v </tex> существует ребро в серую вершину <tex> u </tex>, то это значит, что из вершины <tex> u </tex> существует путь в <tex> v </tex> и из вершины <tex> v </tex> существует путь в <tex> u </tex>. И так как оба эти пути не пересекаются, то существует цикл.