グラフ理論の問題

手順 1：最大次数 $\Delta$ を求め、ヴィジングの定理で範囲を絞る。
各頂点の次数は
$$\mathrm{deg}1=\mathrm{deg}2=\mathrm{deg}3=4,\mathrm{deg}4=\mathrm{deg}5=3$$
である（頂点 $4,5$ は辺 $\{4,5\}$ がない分だけ次数が $1$ 小さい）。よって $\Delta =4$ である。ヴィジングの定理より
$$4\le {\chi }^{\prime }(G)\le 5.$$

手順 2：マッチングの評価で下界を上げる。
辺彩色で同じ色を塗った辺どうしは端点を共有しないので、各色の辺の集合はマッチングになる。頂点数が $5$ なので、マッチングの辺は互いに端点を共有せず、$1$ 本で $2$ 頂点を使うから、マッチングの大きさは $\lfloor 5/2\rfloor =2$ 以下である（例えば $\{1,4\},\{2,3\}$ は大きさ $2$ のマッチング）。よって $\nu (G)=2$。

${\chi }^{\prime }(G)$ 色で塗ると、$9$ 本の辺が各色 $2$ 本以下ずつに分かれるので
$${\chi }^{\prime }(G)\ge \frac{|E|}{\nu (G)}=\frac{9}{2}=\mathrm{4.5.}$$
${\chi }^{\prime }(G)$ は整数なので ${\chi }^{\prime }(G)\ge 5$。

手順 3：結論。
手順 1 の上界 ${\chi }^{\prime }(G)\le 5$ と合わせて ${\chi }^{\prime }(G)=5$。

（確認：実際に $5$ 色で塗れる。色 $a$: $\{1,4\},\{2,3\}$、色 $b$: $\{1,5\},\{2,4\}$、色 $c$: $\{2,5\},\{3,4\}$、色 $d$: $\{1,2\},\{3,5\}$、色 $e$: $\{1,3\}$。各色の辺は端点を共有しない。）

したがって ${\chi }^{\prime }(G)=5$。

$G$ は $K_5$ から辺 $\{4,5\}$ を除いたグラフで、辺数は $9$、最大次数は $\Delta (G)=4$（頂点 $1,2,3$ の次数が $4$、頂点 $4,5$ の次数が $3$）である。

ヴィジングの定理より $\Delta (G)\le {\chi }^{\prime }(G)\le \Delta (G)+1$ なので、${\chi }^{\prime }(G)$ は $4$ か $5$ である。

$4$ 色で足りるか調べる。1 つの色が塗られた辺は互いに端点を共有しないので、同色の辺の集合は 1 つのマッチングになる。頂点が $5$ 個しかないので、マッチングの大きさは高々 $\lfloor 5/2\rfloor =2$ である。よって $4$ 色で塗れる辺は高々 $4\times 2=8$ 本で、辺数 $9$ に足りない。したがって ${\chi }^{\prime }(G)\ge 5$ である。

ヴィジングの定理より ${\chi }^{\prime }(G)\le 5$ なので、${\chi }^{\prime }(G)=5$ となる。

検算として、$5$ 色での具体的な彩色を示す。
- 色1: $\{1,2\},\{3,4\}$
- 色2: $\{1,3\},\{2,4\}$
- 色3: $\{1,4\},\{2,3\}$
- 色4: $\{1,5\},\{2,4\}$ は $\{2,4\}$ が色2と重複するため使えない。そこで色4: $\{1,5\}$ と $\{3,4\}$ も色1と重複するので使えない。

そこで $K_5$ の標準的な $5$ 色彩色を使い、$\{4,5\}$ を除く。$K_5$ は各色が大きさ $2$ のマッチングとなる $5$ 色で塗れる。その色の 1 つに $\{4,5\}$ が含まれるので、これを取り除けば $G$ の $5$ 色彩色が得られる。

以上より ${\chi }^{\prime }(G)=5$。