Subgraf

  Fie G=(X,U) un graf neorientat.

Se numește subgraf al lui G un graf G1=(X1,U1) cu proprietatea că X1 este o submulțime nevidă a lui X, iar U1 conține toate muchiile lui G care au ambele extremități în X1.

  Explicat mai natural, un subgraf conține doar o parte din nodurile grafului inițial, împreună cu toate muchiile care au capetele printre nodurile alese.

Graf neorientat + Subgraf

  Dacă alegem să păstrăm doar nodurile patrulaterului (X1={1,2,3,4}), atât celelalte 3 noduri cât și muchiile [2,5] și [2,6] nu vor apărea. Cele două muchii „scoase” au o extremitate în nodul 2, iar a doua extremitate în 5, respectiv 6, noduri care nu fac parte din submulțimea de noduri a subgrafului.

Numărul total de subgrafuri al lui G este 2n-1.