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

グラフ理論の問題

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

頂点集合を $V = {1, 2, 3, 4, 5}$ とし、辺集合 $E$ を次の $9$ 本の辺からなるものとする単純無向グラフ $G = (V, E)$ を考える（ $G$ は完全グラフ $K_{5}$ から辺 ${4, 5}$ を除いたグラフである）。
${1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}$
$G$ の辺彩色数 $χ^{'} (G)$ を求めよ。ただし、辺彩色とは、共通の端点をもつ 2 本の辺が異なる色になるように各辺に色を塗ることであり、辺彩色数とはそれに必要な色の数の最小値である。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

辺彩色数とヴィジングの定理 $Δ \leq χ^{'} (G) \leq Δ + 1$ を使い、さらに「各色の辺はマッチングになる」ことから下界を作りましょう。

ヒント 2

頂点数が $5$ なので、1 色で塗れる辺（マッチング）は高々 $2$ 本です。 $χ^{'} (G) \geq ∣ E ∣/ ν (G)$ を考えましょう。

ヒント 3

$Δ = 4$ なので $4 \leq χ^{'} (G) \leq 5$ 。また $∣ E ∣ = 9$ 、 $ν (G) = 2$ より $χ^{'} (G) \geq 9/2$ です。

答えと解説

答えを見る

5

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

解説を読む

手順 1：最大次数 $Δ$ を求める。
各頂点の次数は
$de g 1 = de g 2 = de g 3 = 4, de g 4 = de g 5 = 3$
なので $Δ = 4$ である。ヴィジングの定理より
$4 \leq χ^{'} (G) \leq 5.$

手順 2：マッチングを使った下からの評価。
辺彩色で同じ色に塗られた辺どうしは端点を共有しないので、各色の辺の集合はマッチングになる。マッチングに含まれる辺は互いに端点を共有しないから、頂点が $5$ 個のグラフでは 1 つのマッチングに含まれる辺は $⌊ 5/2 ⌋ = 2$ 本以下である。よって最大マッチングの大きさは $ν (G) \leq 2$ （実際 ${1, 2}, {3, 4}$ がマッチングなので $ν (G) = 2$ ）。

色が $k$ 色なら、塗れる辺は高々 $2 k$ 本なので $2 k \geq ∣ E ∣ = 9$ 、すなわち
$χ^{'} (G) \geq \frac{∣ E ∣}{ν ( G )} = \frac{9}{2} = 4.5.$
$χ^{'} (G)$ は整数なので $χ^{'} (G) \geq 5$ である。

手順 3：上下の評価を合わせる。
ヴィジングの定理の上界 $χ^{'} (G) \leq Δ + 1 = 5$ と合わせて
$χ^{'} (G) = 5.$

（確認として、実際に 5 色で塗る例を挙げる。色 a: ${1, 2}, {3, 4}$ 、色 b: ${1, 3}, {2, 5}$ 、色 c: ${1, 4}, {3, 5}$ 、色 d: ${1, 5}, {2, 3}$ 、色 e: ${2, 4}$ 。どの色も端点を共有しない。）

したがって答えは $5$ である。

別解

最大次数は頂点 1,2,3 の次数 4 なので $χ^{'} (G) \geq Δ = 4$ である。しかし 5 頂点のグラフでは、同じ色の辺は互いに端点を共有しないので、1 つの色の辺は高々 $⌊ 5/2 ⌋ = 2$ 本である。辺は 9 本あるので、色数を $k$ とすると $2 k \geq 9$ より $k \geq 5$ 。よって $χ^{'} (G) \geq 5$ 。
一方、 $G$ は $K_{5}$ の部分グラフであり、 $K_{5}$ は 5 本の色で辺彩色できる。具体例は、頂点を $0, \dots, 4$ とし辺 ${i, j}$ を色 $i + j mod 5$ で塗る方法である。同じ頂点 $i$ に接する辺 ${i, j}$ と ${i, k}$ は $j \neq = k$ なら色が異なるので、これは正しい辺彩色になる。この塗り方を $G$ に制限すれば 5 色で塗れる。(ヴィジングの定理 $χ^{'} \leq Δ + 1 = 5$ からも分かる。)
したがって $χ^{'} (G) = 5$ 。

グラフ理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題