Podgraf je časť grafu, ktorá vznikne z pôvodného grafu vymazaním niektorých jeho vrcholov, všetkých hrán vedúcich do týchto vrcholov, poprípade vymazaním ďalších jeho hrán.
Pojem podgraf sa v teórii grafov používa ako istá obdoba pojmu podmnožina.
thumb|Pôvodný graf a jeho podgraf
Graf H je podgraf grafu G, ak a
Indukovaný podgraf thumb|Pôvodný graf a jeho indukovaný podgraf Graf H je indukovaný podgraf grafu G, ak a
Indukovaný podgraf vznikne vymazaním niektorých vrcholov a iba tých hrán, ktoré do vymazaných vrcholov zasahujú.
Faktor Podgraf H je faktor grafu G, ak množina vrcholov grafu H je totožná s množinou vrcholov grafu G. V(H) = V(G)
Kostra Kostra grafu G je taký jeho faktor, ktorý neobsahuje kružnice a je súvislý.
Pozri aj Graf
Kategória:Teória grafov