Лемма о белых путях

Лемма:

Не существует такого момента выполнения поиска в глубину, в который бы существовало ребро из черной вершины в белую.

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Следствие

Лемма о белых путях.

Лемма:

олололо

Доказательство:

[math]\triangleright[/math]

олололо

[math]\triangleleft[/math]