Podgraf

Termín podgraf se v teorii grafů používá jako jistá obdoba pojmu podmnožina.

Graf ${\displaystyle H=(V_{H},E_{H})}$ je podgraf grafu ${\displaystyle G=(V_{G},E_{G})}$, jestliže platí následující podmínky:

1. ${\displaystyle V_{H}\subseteq V_{G}}$
2. ${\displaystyle E_{H}\subseteq E_{G}}$
3. Hrany grafu ${\displaystyle H}$ mají oba vrcholy v ${\displaystyle H}$.

Jinými slovy, podgraf vznikne vymazáním některých vrcholů původního grafu, všech hran do těchto vrcholů zasahujících a případně některých dalších hran.