Realizaremos a demonstração por indução.
Para tal, defina
, e
para cada ,
.
Se , então por construção
. Também, como ,
, para todo , e
tem apenas o caminho unitário, .
Assim,
|
|
|
|
|
|
|
|
A seguir, suponha que para todo
,
e
tome . Como todo caminho direcionado que
chega em a partir de
tem como penúltimo elemento um pai de ,
podemos escrever
|
|
|
|
(7) |
Portanto, obtemos:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
∎