https://kanpurin.hatenablog.com/entry/2021/04/25/054305

問題概要

${N}$ 頂点 ${M}$ 辺の単純無向グラフの各頂点を赤，緑，青で塗り分ける方法で隣接する頂点が異なる色で塗られているようなものは何通りあるか．

${1\leq N \leq 20\\ 0 \leq M \leq \frac{N(N-1)}{2}}$

問題概要2

グラフ理論っぽく書かれていますが，同じ箱に入れてはいけないようなボールの組がいくつか与えられるので区別できる ${N}$ 個のボールを区別できる ${3}$ つの箱にいれる方法の数を求める問題です．

解説

重要な考え方として，複雑な問題をいきなり解くのではなく単純な問題から考えるようにするとうまくいくことがあります．

今回の問題で言うと， ${3}$ 色に塗り分ける問題をいきなり解くのではなくて赤と緑の ${2}$ 色に塗り分ける問題を考えます．ある頂点を赤で塗ると，その頂点と隣接する頂点は青に塗られます．これを繰り返していくと ${1}$ つの連結成分につき，最初の頂点を赤に塗るか青に塗るかの ${2}$ 通りになります．ただし，グラフに奇閉路が存在する場合は ${2}$ 色に塗ることはできません．以上から，奇閉路が存在すれば ${0}$ 通り，存在しなければ連結成分数を ${C}$ として ${2^C}$ が答えになります．