A BFS és a DFS algoritmusok végrehajtása során a gráfnak egy-egy feszítőfáját kapjuk. Ezeket rendkívül frappáns módon BFS és DFS fának nevezzük. Mindketten az eredeti gráf feszítőfái. Csak hát az a baj, hogy a BFS és DFS fák megalkotása során nagy szerepe van a véletlennek. Ha például itt egy másik élt húzunk be… akkor egy egészen más BFS fát kapunk. Arról nem is beszélve, hogy az algoritmus elején a gráf bármelyik csúcsából indulhatunk. Mindezen gubancok ellenére megpróbálhatjuk rekonstruálni az eredeti gráfot annak BSF és DSF fái alapján. Íme, egy gráf két különböző kezdőpont alapján készített BFS fája: Adjuk meg az eredeti gráfot. Lássuk, hogyan tudnánk hasznosítani a BFS fákat. Készítünk egy ilyen kis szomszédsági táblázatot. Aztán pedig kezdjük is az első BFS fával. Eddig jó. Vannak még kétségek, de ezeket reméljük a másik BFS fa hamarosan eloszlatja. Az, hogy a C és D csúcsok között vezet él, immár biztosabb, mint a halál. Hát, ez kész. Már csak föl kell rajzolnunk. Csodás. Egy gráfban minden csúcs fokszáma páros, és két különböző kezdőpont alapján készített BFS fája: Hát, úgy tűnik eddig jutottunk. Nem baj, azért kezdjünk el rajzolgatni. Ezek itt a kérdőjeles élek. Viszont tudjuk még, hogy a gráf minden csúcsának a fokszáma páros. Ha mindkét élt elhagyjuk, az nem jó, mert akkor lesz páratlan fokszámú csúcs. És, ha mindkét élt behúzzuk, az se jó, mert akkor keletkezik harmadfokú csúcs. Ha csak az egyik élt húzzuk be… akkor így lesz egy elsőfokú csúcs. Így viszont minden csúcs páros fokszámú.