Изменения

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