Feszített részgráf hurokél-nélküli gráfokban


R hurokél-nélküli gráf egy G hurokél-nélküli gráf részgráfja, a R megkapható G-ből pontok elhagyásával.

A fenti elhagyások halmaza lehet üres is. Azaz G a G hurokél-nélküli gráf feszített részgráfja. Ha ezt ki akarjuk zárni, akkor valódi részgráfról beszélünk.


Egy alternatív definíció a következő: R=(V', E ', f') hurokél-nélküli gráf a G=(V,E,f) hurokél-nélküli gráf feszített részgráfja, ha V' a V részhalmaza, E ' az {e: f(e) V' része} élhalmaz és f' pedig f' megszorítása E '-re.