Podgraf

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.

Graf H je podgraf grafu G, ak  a

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

Teória grafov