Megjegyzés: Ha G egy összefüggő gráf és egy új élt adunk hozzá, amely G két csúcsát köti; össze akkor nyilván egy összefüggő gráfot kapunk. (Az összefüggőség egy monoton tulajdonság. Egy gráftulajdonság monotonitását mindenki megpróbálhatja definiálni.)
Ezen megjegyzés után a következőt mondhatjuk: Ha G összefüggő és egy e éle elhagyásával kapott G-e gráf is összefüggő, akkor G összefüggőségének okát kutatva ezt G-e-ben is meg kell találnunk. Ezekután már természetes a következő algoritmus:
Algoritmus: Adott egy G összefüggő gráf. Output: G egy feszítő részgráfja.
Rendezési lépés: Rendezzük sorba G éleit: e1, e2, e3,...
Tesztelő lépések: A fenti rendezés szerint haladjunk végig az összes élen és minden e élnél végezzük el a következőeket. Az aktuális gráfunk legyen A. Ha A-e összefüggő, akkor aktuális gráfunk legyen A-e. Ha A-e nem összefüggő, akkor aktuális gráfunk maradjon meg A-nak.
A tesztelő lépések utáni aktuális gráf az algoritmus outputja.
Lemma:
A fenti eljárás az input G gráf egy F feszítő részgráfja,
amelyre teljesül, hogy
(i)
F összefüggő,
(ii)
F bármely e élére F-e nem összefüggő.
A fenti lemma alapján természetes a következő fogalom bevezetése:
Definíció: Egy gráfot fának nevezünk, ha összefüggő és bármely élet elhagyva nem összefüggővé válik.
Megjegyzés: A fa elnevezés alapja ebben a pillanatban nem világos. A későbbiekben ez a név is természetessé válik.
A fentiekből kiolvasható a következő egyszerű állítás.
Lemma: Egy gráf akkor és csak akkor összefüggő, ha van feszítő részgráfja, amely fa.
Bizonyítás:
Ha gráfunknak van fa (speciálisan
összefüggő) feszítő részgráfja,
akkor gráfunk ezen összefüggő gráfból nyerhető élek
hozzáadásával, így maga is összefüggő.
Ha gráfunk összefüggő, akkor
a fenti algoritmus egy fa feszító részgráfot ad.
Definíció: Egy gráf feszítőfája egy fa feszítő részgráf.
A fentiekből nyilvánvaló, hogy pontosan az összefüggő gráfoknak van feszítőfája és minden összefüggő gráf felfogható, mint egy fa (egy feszítőfája) plusz esetleg további behúzott élek. Ezek után természetes a fák tanulmányozása.
Tétel:
Legyen F egy gráf. ekkor a következők ekvivalensek
(i) F fa, azaz összefüggő és bármely élet elhagyva megszűnik
összefüggősége (F minimális összefüggő gráf),
(ii) F összefüggő és nincs benne kör,
(iii) F-ben nincs kör, de tetszőleges élt hozzáadva
keletkezik kör (F maximális körmentes gráf),
(iv) F bármely két pontja között pontosan egy út
létezik.
Bizonyítás:
(i)=>(ii)
A következő lemmából következik az implikáció:
Lemma:
Legyen G egy gráf és e egy C körének egy éle.
(a)
Ha G összefüggő, akkor G-e is az,
(a)* V(G)=V(G-e)-n a ~G és ~G-e ugyanaz a reláció
(azaz G és G-e komponens struktúrája ugyanaz).
Lemma bizonyítása:
Elegendő (a)*-t bizonyítani, ami (a) egy erősítése.
Ha x és y közt nincs séta G-ben, akkor természetesen
G-e-ben sincs.
Ha x és y közt van séta G-ben, akkor út is van.
Ha ez nem tartalmazza az e élt,
akkot ez egy xy séta g-e-ben is.
Ha ez tartalmazza e-t (út mivolta miatt pontosan egyszer),
akkor sétánk ezen lépését helyettesíthetjük
C e-n kívüli ívével. Ez a módosítás
egy G-e-beli xy sétához vezet.
(ii)=>(iii)
(iii)=>(iv)
(iv)=>(i)
Feszítőfa: Egy G összefüggő gráf minimális összefüggő feszítő részgráfjai= maximális körmentes feszítő részgráfjai= G feszítőfái.