縮約・マイナー・禁止マイナー

辺 $e=xy$ の縮約 $G/e$ は、$G$ から $x,y$ を除いて新しい頂点 $v_e$ を足し、$v_e$ を $(N(x)\cup N(y))\setminus\{x,y\}$ の各頂点と隣接させたグラフである（$x$ と $y$ の共通の隣接点への辺は 1 本にまとめる）。

グラフ $X$ が $G$ のマイナーであるとは、互いに交わらない空でない集合 $V_x\subseteq V(G)$（$x\in V(X)$）で、各 $G[V_x]$ が連結で、$xy\in E(X)$ ならば $V_x$ と $V_y$ を結ぶ $G$ の辺があるものが取れることをいう。$V_x$ を枝集合、族 $(V_x)$ を $X$ の模型と呼ぶ。

グラフの族 $\mathcal{P}$ がマイナーで閉じるとは、$G\in\mathcal{P}$ のマイナーがすべて $\mathcal{P}$ に属することをいう。このとき、$\mathcal{P}$ に属さないグラフのうち、マイナーの関係について極小なものを $\mathcal{P}$ の禁止マイナーという。