Definitie subgraf

Definiţie : Un subgraf al unui graf G=(V,U) este un graf H(V1,U1) astfel încât V1 este inclus in V iar U1 conţine toate muchiile din U care au ambele extremităţi în V1 (un subgraf se obţine eliminând vârfuri din V şi muchiile incidente acestor vârfuri). Vom spune că subgraful H este indus sau generat de mulţimea de vârfuri V1.