Začneme tým, že si uvedieme a vysvetlíme definíciu podgrafu.



Uvedená definícia nám hovorí, že ak máme daný graf, tak jeho podgraf zostrojíme tak, že si z neho vyberieme hociktoré jeho vrcholy a hociktoré hrany incidentné s týmito vrcholmi. Z toho okrem iného vyplýva, že každý graf je podgrafom samého seba.

Na obrázku je znázornený graf a tri jeho podgrafy.