Subgraf

Un subgraf al grafului G=(X,U) este un graf G1=(Y,V) astfel încât Y este o submultime a lui X(numarul de noduri ale lui Y sunt incluse in multimea lui X) iar mulțimea de muchii V este de asemenea o submulțime a lui U. Rezulta un graf cu numar diferit de noduri (se sterge un nod si muchiile incidente acestuia).