Изменения

Пусть в процессе выполнения процедуры <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>, и она будет покрашена в черный цвет. Получаем противоречие.

Пусть дан граф <tex>G</tex>. Запустим <tex>dfs(G)</tex>. Остановим выполнение процедуры <tex>dfs</tex> от какой-то вершины <tex>u</tex> графа <tex>G</tex> в тот момент, когда вершина <tex>u</tex> была выкрашена в серый цвет (назовем его нулевым первым моментом времени). Заметим, что в данный момент в графе <tex>G</tex> есть как белые, так и черные, и серые вершины. Продолжим выполнение процедуры <tex>dfs(u)</tex> до того момента, когда вершина <tex>u</tex> станет черной (первый второй момент времени).Тогда вершины графа <tex>G\setminus u</tex>, бывшие черными и серыми в нулевой момент времени, не поменяют свой цвет в к первый момент времени, а белые вершины либо останутся белыми, либо станут черными, причем черными станут те, что были достижимы от вершины <tex>u</tex> по белым путям.