この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

グラフ理論の問題

難易度 1教科書の例題レベル大学数学グラフ理論

頂点集合 $V = {1, 2, 3, 4, 5}$ と、次の $7$ 本の辺からなる辺集合 $E$ をもつ単純無向グラフ $G = (V, E)$ を考える。
${1, 3}, {1, 4}, {1, 5}, {2, 4}, {2, 5}, {3, 4}, {3, 5}$
同じ頂点を端点にもつ辺どうしが異なる色になるように辺を塗り分けるとき、必要な色の数の最小値（辺彩色数） $χ^{'} (G)$ を求めよ。

この問題で使うもの

辺彩色数とヴィジングの定理（説明と入口の問題）

この問題を解けるようになるまで（10 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

辺彩色数とヴィジングの定理を使います。まず最大次数 $Δ$ を求め、 $Δ \leq χ^{'} (G) \leq Δ + 1$ で候補をしぼりましょう。

ヒント 2

同じ色の辺はマッチングになります。頂点が $5$ 個なので 1 色で塗れる辺は何本までか考え、 $χ^{'} (G) \geq ∣ E ∣/ ν (G)$ を使いましょう。

ヒント 3

$Δ = 3$ なので $3 \leq χ^{'} (G) \leq 4$ 。また $ν (G) \leq 2$ なので、 $7$ 本の辺を塗るには $χ^{'} (G) \geq 7/2$ が必要です。

答えと解説

答えを見る

4

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

手順1：最大次数 $Δ$ を求め、ヴィジングの定理で範囲をしぼる。
各頂点の次数は
$de g 1 = 3, de g 2 = 2, de g 3 = 3, de g 4 = 3, de g 5 = 3$
である（合計 $14 = 2 \times 7$ で握手補題とも合う）。よって $Δ = 3$ であり、ヴィジングの定理より
$3 \leq χ^{'} (G) \leq 4.$

手順2：マッチングによる下からの評価。
辺彩色では、同じ色の辺は端点を共有しないので、各色の辺の集合はマッチングになる。頂点は $5$ 個しかないので、1 つのマッチングに含まれる辺は高々 $⌊ 5/2 ⌋ = 2$ 本、すなわち $ν (G) \leq 2$ である。 $7$ 本の辺を、各色 $2$ 本以下で塗り分けるので
$χ^{'} (G) \geq \frac{∣ E ∣}{ν ( G )} \geq \frac{7}{2} = 3.5.$
$χ^{'} (G)$ は整数なので $χ^{'} (G) \geq 4$ である。

手順3：結論。
手順1の $χ^{'} (G) \leq 4$ と合わせて $χ^{'} (G) = 4$ 。

（確認）実際に、次の $4$ 色で塗り分けられる：色1 ${1, 3}, {2, 4}$ 、色2 ${1, 4}, {2, 5}$ 、色3 ${1, 5}, {3, 4}$ 、色4 ${3, 5}$ 。どの色も端点を共有しない。

よって $χ^{'} (G) = 4$ 。

別解

各頂点の次数は、頂点1が3（辺の端点が3,4,5）、頂点2が2、頂点3が3、頂点4が3、頂点5が3である。最大次数は $Δ = 3$ なので $χ^{'} (G) \geq 3$ である。

しかし頂点は5個なので、同じ色の辺は端点を共有しない。したがって、1つの色の辺は互いに素な辺の集合（マッチング）であり、その大きさは高々 $⌊ 5/2 ⌋ = 2$ である。3色では辺を高々 $3 \times 2 = 6$ 本しか塗れないが、辺は7本あるので3色では足りない。よって $χ^{'} (G) \geq 4$ 。

一方、ヴィジングの定理より $χ^{'} (G) \leq Δ + 1 = 4$ である。

念のため4色での塗り分けを具体的に示す。色1: {1,3},{2,4}、色2: {1,4},{2,5}、色3: {3,5}、色4: {1,5},{3,4}。
色4の {1,5} と {3,4} は端点を共有しない。他の色も同様に端点を共有しない。7本すべてが塗られている。

よって $χ^{'} (G) = 4$ 。

グラフ理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題