グラフ理論の問題

基本的な量. 頂点数は $\left(\genfrac{}{}{0ex}{}{7}{3}\right)=35$。頂点 $A$ と隣接する頂点は、$A$ の補集合（4 元集合）に含まれる 3 元部分集合なので、その個数は $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$。よって $G$ は 4-正則で、辺の数は $\frac{35\cdot 4}{2}=70$ である。

彩色数.

(下界) 次の 7 個の頂点
$$\{1,2,3\},\{4,5,6\},\{7,1,2\},\{3,4,5\},\{6,7,1\},\{2,3,4\},\{5,6,7\}$$
は、隣り合うもの（最後と最初も含む）がすべて互いに素なので、長さ 7 の閉路をなす。奇閉路があるので $G$ は 2 部グラフでなく、$\chi (G)\ge 3$。

(上界) 頂点 $A$ に次のように色を塗る。
- $1\in A$ なら色 1
- $1\notin A,2\in A$ なら色 2
- $1,2\notin A$（すなわち $A\subset \{3,4,5,6,7\}$）なら色 3

色 1 の頂点どうしは要素 1 を共有し、色 2 の頂点どうしは要素 2 を共有するので隣接しない。色 3 の頂点は 5 元集合 $\{3,4,5,6,7\}$ の 3 元部分集合で、$3+3>5$ より任意の 2 つは交わるので隣接しない。よってこれは正しい 3 彩色であり、$\chi (G)\le 3$。

以上より $\chi (G)=3$。（これはロヴァースの定理 $\chi (K(n,k))=n-2k+2$ とも一致する。）

辺彩色数.

ヴィジングの定理より、最大次数 $\Delta =4$ の単純グラフでは $\Delta \le {\chi }^{\prime }(G)\le \Delta +1$、すなわち $4\le {\chi }^{\prime }(G)\le 5$。

辺彩色で同じ色の辺の集合はマッチングである。頂点数が 35（奇数）なので、1 つのマッチングに含まれる辺は高々 $\lfloor \frac{35}{2}\rfloor =17$ 本。4 色で塗れたとすると、塗れる辺は高々 $4\cdot 17=68$ 本であり、辺の数 70 に足りない。よって ${\chi }^{\prime }(G)\ne 4$ で、${\chi }^{\prime }(G)=5$。

答えは $(\chi (G),{\chi }^{\prime }(G))=(3,5)$。

$G=K(7,3)$ は頂点数 $\left(\genfrac{}{}{0ex}{}{7}{3}\right)=35$、各頂点の次数は残り 4 元から 3 元を選ぶ $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ の 4-正則グラフ（奇グラフ $O_4$）である。辺数は $35\cdot 4/2=70$。

【彩色数】クネーザーグラフの彩色数に関するロヴァースの定理（Lovász–Kneser の定理）より $\chi (K(n,k))=n-2k+2$。$n=7,k=3$ なので $\chi (G)=7-6+2=3$。
確認: 3 色で塗れる例は、元 1 を含む集合を色 1、元 1 を含まず元 2 を含む集合を色 2、残り（$\{3,4,5,6,7\}$ の 3 元部分集合、5 元中 3 元どうしは必ず交わる）を色 3 とすればよい。各色の集合は互いに交わる（色 1 は 1 を共有、色 2 は 2 を共有、色 3 は 5 元中の 3 元どうしで $3+3>5$ より交わる）ので、同色の頂点は隣接せず、3 色で正しく彩色できる。また辺があるので 2 色以下は不可能でないことは、三角形 $\{1,2,3\},\{4,5,6\},\{1,4,7\}$ ではなく、例えば $\{1,2,3\},\{4,5,6\}$ に加え 3 つ目が両方と交わる必要があるが、奇数長閉路 $O_4$ は奇閉路 5 を含む（$\chi \ge 3$ はロヴァースの定理による）ので $\chi =3$。

【辺彩色数】最大次数 $\Delta =4$ なので ${\chi }^{\prime }\ge 4$、ヴィジングの定理より ${\chi }^{\prime }\le 5$。もし ${\chi }^{\prime }=4$ なら、各色類は完全マッチング（35 頂点を被覆）になるはずだが、頂点数 35 は奇数なので完全マッチングは存在しない。実際、1 つの色類（マッチング）の大きさは高々 $\lfloor 35/2\rfloor =17$ なので、4 色では高々 $4\cdot 17=68<70$ 辺しか塗れない。よって ${\chi }^{\prime }\ge 5$。ゆえに ${\chi }^{\prime }(G)=5$。

答え: $(\chi (G),{\chi }^{\prime }(G))=(3,5)$。