Nyilvánvaló, hogy a mélységi kereséssel kapott faváznak megvan a második kérdésben követelt tulajdonsága. Legyen ugyanis uv a gráf egy éle. Feltehetjük, hogy a keresés során u és v közül eloször u került sorra. Amikor elértünk u-hoz, akkor minden ezután beválasztott pont u utódja lesz a fán, amíg csak u-ból „vissza nem lépünk”. De vissza csak akkor lépünk, ha már u minden szomszédja szerepel, tehát eddigre a v pont sorra kerül. Tehát: a v pont u után és az u-ról való visszalépés között kerül sorra, de ez azt jelenti, hogy v biztosan u utódja lesz a fán.
| TARTALOMJEGYZÉK |