Mycielski の構成

グラフ $G$（頂点 $v_1,\dots,v_n$）に対し、新しい頂点 $v_1',\dots,v_n'$ と $w$ を足し、辺を

• $G$ の辺、
• $v_iv_j\in E(G)$ のときの $v_i'v_j$ と $v_iv_j'$、
• $v_i'w$（$i=1,\dots,n$）

としたグラフを $M(G)$ と書く。頂点は $2n+1$ 個、辺は $3m+n$ 本である。