Subgraph oder Untergraph H eines GraphenG, ein Graph, der aus einer Eckenmenge E(H) ⊆ E(G) und einer Kantenmenge K(H) ⊆ K(G) besteht. Man sagt dann auch, daß G ein Obergraph oder Supergraph von H sei. Gilt zusätzlich E(H) = E(G), so ist H ein Faktor, erzeugender oder aufspannender Untergraph von G.

Es sei G ein Graph und A ⊆ E(G). Derjenige Teilgraph von G, der aus der Eckenmenge A und allen Kanten von G besteht, die nur mit Ecken aus A inzidieren, heißt der von A induzierte Teilgraph, in Zeichen G[A].

Es seien G ein Graph, E′ ⊂ E(G) und K′ ⊆ K(G). Derjenige Teilgraph von G, der aus K′ und allen Ecken von G besteht, die mit Kanten aus K′ inzidieren, heißt der von K′ induzierte Teilgraph, in Zeichen G[K′ ]. Für den induzierten Teilgraphen G[E(G) \ E′ ] schreibt man kurz G − E′, und der Faktor G − K′ besitzt die Eckenmenge E(G) und die Kantenmenge K(G) − K′. Besteht E′ nur aus einer einzigen Ecke v oder K′ nur aus einer einzigen Kante k, so schreibt man auch G − v für G − {v} und G − k für G − {k}. Anschaulich gesprochen ist G − E′ durch das Entfernen von Ecken bzw. G − K′ durch das Entfernen von Kanten entstanden.

Auch das Hinzufügen von Kanten ist eine wichtige Operation in der Graphentheorie. Es seien x und y zwei nicht adjazente Ecken eines Graphen G. Fügt man zu G eine neue Kante k = xy hinzu, so schreibt man dafür G + k oder G + xy.

Einen vollständigen Teilgraphen H eines Graphen G nennt man Clique von G. Die Ordnung einer größten Clique in G heißt Cliquenzahl von G, in Zeichen ω(G).