I. ELJÁRÁS (Feszítő fa keresése összefüggő gráfban):

1. LÉPÉS:

Válasszuk ki a G gráf egy tetszőleges x₁ pontját, ez a pont pontja lesz a G’ részgráfnak.

2. LÉPÉS:

Ha a gráfnak x₁-en kívül nincs több pontja, befejezzük az eljárást.

Ha a gráfnak x₁-en kívül is van pontja, akkor keressünk egy olyan x₂ pontot, amely össze van kötve x₁-gyel. Ilyen pontnak kell lennie, különben a gráf nem volna összefüggő. Az x₂ pontot és az x₁x₂ élt beválasztjuk a G’ részgráfba.

k. LÉPÉS:

Tegyük fel, hogy az x₁, x₂, …, x_k–1 pontokat már kiválasztottuk.

Ha az {x₁, x₂, …, x_k–1}=A halmaz tartalmazza a G gráf összes pontját, akkor befejezzük az eljárást.

Ha az {x₁, x₂, …, x_k–1}=A halmaz nem tartalmazza a G gráf összes pontját, akkor (D) szerint van olyan él, amely A és a gráf többi pontja között fut, vagyis egy A-beli x_i pontot köt össze egy A-n kívüli x_k ponttal. Az x_k pontot és az x_ix_k élt beválasztjuk a G’ részgráfba. (Az alábbi ábrán i=2 és k=8.)

Ha G-nek n pontja van, akkor az eljárás pontosan az n-edik lépésben ér véget és az első lépés kivételével minden lépésben a G gráf egy új élét választja ki és veszi hozzá G’-höz. Ebből következik:

Az I. eljárással kapott G’ részgráf a G gráf összes pontját tartalmazza. Ha G-nek n pontja van, akkor G’-nek n–1 éle van.