部分グラフ・補グラフ・特別なグラフ

$V(H)\subseteq V(G)$ かつ $E(H)\subseteq E(G)$ であるグラフ $H$ を $G$ の部分グラフといい、$V(H)=V(G)$ のとき全域部分グラフという。$S\subseteq V(G)$ に対し、頂点集合が $S$ で、両端が $S$ に入る $G$ の辺すべてを辺とするグラフ $G[S]$ を誘導部分グラフという。$G-S=G[V(G)\setminus S]$、$G-e$（辺 $e$ だけを除く）、$G+uv$（辺 $uv$ を足す）と書く。補グラフ $\overline G$ は、頂点集合が同じで、$uv\in E(\overline G)\iff uv\notin E(G)$（$u\ne v$）で定める。

• 完全グラフ $K_n$: $n$ 頂点のどの 2 つも隣接する。
• 二部グラフ: $V(G)=A\sqcup B$ と分割でき、どの辺も $A$ の頂点と $B$ の頂点を結ぶ。$(A,B)$ を二部分割という。
• 完全二部グラフ $K_{m,n}$: $|A|=m$、$|B|=n$ で、$A$ の各頂点が $B$ の全頂点と隣接する二部グラフ。
• 閉路グラフ $C_n$、道グラフ $P_n$: $n$ 頂点の閉路、$n$ 頂点の道だけからなるグラフ。