Un subgraf generat al unui grafic este un alt grafic format dintr-un subset de vârfuri ale graficului împreună cu toate muchiile care conectează perechile de vârfuri din acel subset.
Formal, fie G = ( V , E ) orice graf, și fie S ⊂ V o submulțime de vârfuri în G . Atunci subgraful generat G [ S ] este un grafic ale cărui vârfuri sunt elemente ale lui S , și ale cărui muchii constau din toate muchiile din mulțimea E , ale căror vârfuri finale aparțin lui S [1] . Aceeași definiție se aplică graficelor nedirecționate , graficelor direcționate și chiar multigrafurilor .
Un subgraf generat G [ S ] poate fi numit și un subgraf generat în G de un set de vârfuri S sau (dacă contextul nu duce la ambiguitate) un subgraf generat de vârfuri S .
Tipurile importante de subgrafe sunt următoarele:
Problema izomorfismului subgrafului generat este un tip de problemă de căutare a subgrafului izomorf în care scopul este de a testa dacă un grafic poate fi găsit ca subgraf generat al altui grafic. Deoarece această problemă include problema clicei ca caz special, este NP-complet [4] .