Teilgraph

G₁=(V₁,E₁) heißt Teilgraph oder Subgraph von G₂=(V₂,E₂), falls V₁ Teilmenge von V₂ und

in Graphen ohne Mehrfachkanten E₁ Teilmenge von E₂ ist,
in ungerichteten Graphen mit Mehrfachkanten E₁(e)≤E₂(e) für alle zweielementigen Teilmengen e von V₂ gilt,
in gerichteten Graphen mit Mehrfachkanten E₁(e)≤E₂(e) für alle e aus dem kartesischen Produkt V₂xV₂ gilt.

Gilt zusätzlich:

in Graphen ohne Mehrfachkanten, e ist Element von E₂ für alle e aus E₁,
in ungerichteten Graphen mit Mehrfachkanten, E₁(e)=E₂(e) für alle zweielementigen Teilmengen e von V₂,
in gerichteten Graphen mit Mehrfachkanten, E₁(e)=E₂(e) für alle e aus dem kartesischen Produkt V₂xV₂,

so bezeichnet man G₁ auch als den durch V₁ induzierten Teilgraph von G₂.

Bemerkung: Induizerte Teilgraphen sind immer eindeutig durch die entsprechende Knotenmenge festgelegt.

kommen noch.