Ahogy a szélességi keresésre (II. eljárás), úgy a mélységi keresésre (III. eljárás) is igaz, hogy ha eljut egy ponthoz, akkor annak összes szomszédjához is eljut. Hiszen a gyökérhez csak akkor jut vissza, ha már minden pontból kimerítette az összes továbblépési lehetőségeket, tehát minden pont minden szomszédját bejárta. Vagyis az eljárás által bejárt pontok halmazából nem vezet ki él. Minthogy a gráf összefüggő, ebből már (D) szerint következik, hogy a gráf minden pontja sorra került. Ebből viszont a dőlt betűs állítás szerint következik, hogy minden élt is bejárt.
| TARTALOMJEGYZÉK |