グラフ彩色（隣接は別色）
隣り合う頂点を別の色に塗る。最小何色で塗れるか＝彩色数 χ（カイ）。
グラフを選ぶ
3
使用色数
—
競合数（隣接同色の辺）
—
彩色数 χ（このグラフ）
—
—
頂点をクリック／タップで色を順送り。ドラッグで動かせます（辺は固定）。隣接が同じ色だと辺が赤く太くなります。
グラフ彩色とは、辺でつながった頂点どうしが必ず違う色になるように、各頂点へ色を割り当てる塗り分けです。地図の隣り合う国を別色で塗る問題や、時間割・周波数割り当てと同じ構造をしています。
あるグラフを塗るのに最低限必要な色数を彩色数 χ（カイ）と呼びます。これはアルゴリズムの手順ではなく、グラフそのものが持つ構造（不変量）です。プリセットを切り替え、頂点をクリックして手で塗り分けたり、貪欲彩色を試したりして、何色で塗り切れるか確かめましょう。
あるグラフを塗るのに最低限必要な色数を彩色数 χ（カイ）と呼びます。これはアルゴリズムの手順ではなく、グラフそのものが持つ構造（不変量）です。プリセットを切り替え、頂点をクリックして手で塗り分けたり、貪欲彩色を試したりして、何色で塗り切れるか確かめましょう。
いま何が起きている？
ここがポイント
- 隣接頂点は必ず異色 ── これが守れていない辺＝競合。競合 0 になって初めて「正しい彩色」。
- 最小色数 ＝ 彩色数 χ ── そのグラフを塗れる色数の下限で、グラフ固有の不変量。奇サイクルは χ=3、二部グラフは χ=2。
- 平面グラフは必ず 4 色以内で塗れる（四色定理） ── 地図のように平面に交差なく描けるグラフは χ ≤ 4。
- 貪欲彩色は順序で色数が変わる ── 同じグラフでも頂点を見る順番（次数順／番号順）次第で使う色数が増減する。χ の達成は順序選び次第。