Nachbarschaft eines Knotens $v \in V$: $N^+(v) = \{u\in V \mid (v,u) \in E\}$, $N^-(v) = \{u\in V \mid (u,v) \in E\}$. $N(v) = N^+(v) \cup N^-(v)$.
Grad eines Knotens $d^+(v) = |N^+(v)|$, $d^-(v) = |N^-(v)|$, $d(v) = |N(v)|$
Weg: Folge von Knoten $\{v_1, v_2, \ldots ,v_k\}$, so dass $(v_i, v_{i+1}) \in E \; \forall i=1,\ldots, k-1$.
Zyklus: Weg mit $v_1=v_k$.
Zusammenhängender Graph: Für alle Knotenpaare gibt es einen Weg von einen zum anderen.
Baum: Zusammenhängender Graph ohne Zyklus.
Kompletter Graph: Alle möglichen Kanten existieren.
Planarer Graph: Kann in der Ebene ohne Kantenüberschneidungen gezeichnet werden.