Der Begriff
Teilgraph beschreibt in der
Graphentheorie eine Beziehung zwischen zwei
Graphen. Ein anderes Wort für Teilgraph ist
Untergraph. Ein Graph
![](http://info.babylon.com/onlinebox.cgi?rt=GetFile&uri=!!DZ6P2U34SE&type=0&index=162)
ist Teilgraph des Graphen
![](http://info.babylon.com/onlinebox.cgi?rt=GetFile&uri=!!DZ6P2U34SE&type=0&index=83)
, wenn alle Knoten und Kanten von
![](http://info.babylon.com/onlinebox.cgi?rt=GetFile&uri=!!DZ6P2U34SE&type=0&index=162)
auch in
![](http://info.babylon.com/onlinebox.cgi?rt=GetFile&uri=!!DZ6P2U34SE&type=0&index=83)
enthalten sind. Anders gesagt: Ein Teilgraph
![](http://info.babylon.com/onlinebox.cgi?rt=GetFile&uri=!!DZ6P2U34SE&type=0&index=162)
entsteht aus einem Graphen
![](http://info.babylon.com/onlinebox.cgi?rt=GetFile&uri=!!DZ6P2U34SE&type=0&index=83)
, indem einige Knoten und Kanten aus
![](http://info.babylon.com/onlinebox.cgi?rt=GetFile&uri=!!DZ6P2U34SE&type=0&index=83)
entfernt werden. Dabei müssen beim Entfernen eines Knotens auch alle
inzidenten Kanten mit entfernt werden.