Dupa sortarea listelor de adiacenta, se efectueaza o parcurgere DF din radacina lui {$G*$}.

_Propozitie 1_: Arborele DF rezultat din parcurgerea de mai sus contine numai muchii de arbore sau muchii inainte.

 
* _Propozitie 1_: Arborele DF rezultat din parcurgerea de mai sus contine numai muchii de arbore sau muchii inainte.

Cum {$G*$} este aciclic, nu pot exista muchii de intoarcere ( inapoi ). Vom demonstra ca nu exista muchii transversale. Definim {$nivel{~x~}$} ca fiind numarul de noduri de la $x$ la radacina parcurgand numai muchii de arbore.
Presupunem prin reducere la absurd ca exista o muchie transversala {$x->y$}. Selectam acea muchie transversala {$x->y$} pentru care {$nivel{~y~}$} este minim. $Y$ nu poate fi radacina lui {$G*$}, pentru ca, in caz contrar, muchia {$x->y$} ar fi muchie de intoarcere si ar forma un ciclu, dar {$G*$} este aciclic. Deci exista un nod $u$ care este tatal lui {$y$}. Demonstram ca pentru tripletul {$(x u y)$} conditia (*) nu este indeplinita.