Subgraf

  Fie G=(X,E) un graf orientat.

Se numește subgraf al lui G un graf G1=(X1,E1), cu proprietatea X1 este o submulțime a lui X și E1=E.

  Subgraful conține mai puține noduri decât graful inițial, dar toate arcele care există între nodurile rămase (care au ambele extremități în X1).

Graf orientat + Subgraf

  Eliminând nodurile divizibile cu 3, ne rămâne mulțimea X1={1,2,4,5,7,8,10}. Nu vor mai apărea arcele spre nodurile {3,6,9}, deoarece ele nu se află în submulțimea de noduri; arcele nu se pot forma fără o extremitate.

Numărul maxim de subgrafuri ale unui graf orientat cu n noduri este 2n-1