Teilgraph

Seien $G, H$ Graphen.

Untergraph a.k.a. Teilgraph: $H$ ist ein Untergraph von $G$ ( $H \subseteq G$ ), wenn $V (H) \subseteq V (G)$ und $E (H) \subseteq E (G)$ .
Induzierter Untergraph: Ein Untergraph $H$ , der alle Kanten aus $G$ enthält, die zwischen den Knoten aus $V (H)$ verlaufen ( $E (H) = E (G) \cap P_{2} (V (H))$ ). Geschrieben als $G [X]$ , wobei $X$ die gewählte Knotenmenge ist.
Spannender Untergraph: Ein Untergraph $H$ , der exakt dieselbe Knotenmenge wie der Ursprungsgraph besitzt ( $V (H) = V (G)$ ).