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).
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