グラフ理論の問題

難易度 3期末試験の応用レベル証明問題大学数学グラフ理論

$G = (V, E)$ を頂点数が $1$ 以上の有限な単純無向グラフとする。 $G$ の頂点彩色数（隣接する 2 頂点が異なる色になるように頂点を塗り分けるのに必要な色の最小数）を $χ (G)$ と書き、 $k = χ (G)$ とおく。頂点 $v$ の次数（ $v$ に隣接する頂点の個数）を $de g v$ と書く。

このとき、 $G$ には $de g v \geq k - 1$ を満たす頂点 $v$ が少なくとも $k$ 個存在することを証明せよ。

この問題で使うもの

頂点彩色と彩色数（説明と入口の問題）
グラフの次数と握手補題（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$k$ 色の正しい彩色を 1 つとり、色ごとの頂点の集合 $V_{1}, \dots, V_{k}$ に分けて考えます。各 $V_{i}$ から次数の大きい頂点を 1 つずつ見つける方針です。

ヒント 2

各 $V_{i}$ の中に「ほかの $k - 1$ 色すべての頂点と隣接する」頂点があることを示せば十分です。そうでないと仮定して、 $V_{i}$ の頂点を別の色に塗りかえることを考えましょう。

ヒント 3

$V_{i}$ のどの頂点 $x$ にも、隣接する頂点をもたない色 $j (x) \neq = i$ があるとします。 $x$ を色 $j (x)$ に塗りかえても、 $V_{i}$ の頂点どうしは隣接しないので衝突は起きません。すると色 $i$ を使わない彩色ができます。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$k$ 色の正しい彩色をとって色クラス $V_{1}, \dots, V_{k}$ に分け、各クラスが空でなく、クラス内の頂点どうしが隣接しないことを述べている（2 点）
各 $V_{i}$ に、ほかのすべての色クラスの頂点と隣接する頂点があることを、背理法で示す方針を立てている（2 点）
そうでないと仮定したとき、 $V_{i}$ の各頂点を隣接頂点のない色に塗りかえた彩色を定め、それが正しい彩色であることを場合分けで確かめ、 $k - 1$ 色で塗れることから矛盾を導いている（4 点）
得られた $k$ 個の頂点が相異なり、それぞれの次数が $k - 1$ 以上であることを示して結論している（2 点）

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

模範解答を読む

$k$ 色の正しい彩色を 1 つ固定し、各色の頂点の中に「ほかのすべての色の頂点と隣接する」頂点があることを背理法で示す。

準備. 頂点数は $1$ 以上なので $k \geq 1$ である。彩色数の定義より、正しい彩色 $c : V \to {1, \dots, k}$ （ $G$ で隣接する $u, v$ について $c (u) \neq = c (v)$ ）が存在する。各 $i \in {1, \dots, k}$ について色 $i$ の頂点全体を $V_{i} = {v \in V ∣ c (v) = i}$ とする。

各 $V_{i}$ は空でない。実際、ある $V_{i}$ が空なら、 $c$ は $k - 1$ 個の色 ${1, \dots, k} ∖ {i}$ だけを使う正しい彩色となり（色の番号をつけ直せばよい）、 $χ (G) = k$ の最小性に反する。また、 $V_{i}$ の 2 頂点は同じ色なので、 $c$ が正しい彩色であることから互いに隣接しない。

主張. 各 $i$ について、 $V_{i}$ には次の性質 $(*)$ をもつ頂点 $x$ が存在する。
$(*) i 以外のすべての色 j について、 x は V_{j} のある頂点と隣接する。$

主張の証明（背理法）. $k = 1$ のときは $i$ 以外の色がないので、 $V_{1}$ の任意の頂点が $(*)$ を満たす（ $V_{1} \neq = \emptyset$ ）。以下 $k \geq 2$ とする。ある $i$ について、 $V_{i}$ のどの頂点も $(*)$ を満たさないと仮定する。すると各 $x \in V_{i}$ について、 $x$ がどの頂点とも隣接しない色クラス $V_{j}$ （ $j \neq = i$ ）が存在するので、そのような $j$ を 1 つ選んで $j (x)$ とおく。新しい彩色 $c^{'}$ を
$c^{'} (x) = {j (x) c (x) (x \in V_{i}) (x \in / V_{i})$
と定める。 $c^{'}$ の値は ${1, \dots, k} ∖ {i}$ に入る。 $c^{'}$ が正しい彩色であることを示す。隣接する 2 頂点 $x, y$ をとる。
- $x, y$ がともに $V_{i}$ に属さないとき: $c^{'} (x) = c (x) \neq = c (y) = c^{'} (y)$ 。
- $x, y$ がともに $V_{i}$ に属するとき: $V_{i}$ の 2 頂点は隣接しないので、この場合は起こらない。
- 一方だけ、たとえば $x$ が $V_{i}$ に属し $y$ が属さないとき: $j (x)$ の選び方より $x$ は色 $j (x)$ の頂点と隣接しないので、 $x$ に隣接する $y$ について $c (y) \neq = j (x)$ である。よって $c^{'} (y) = c (y) \neq = j (x) = c^{'} (x)$ 。

したがって $c^{'}$ は $k - 1$ 個の色を使う $G$ の正しい彩色であり、 $χ (G) = k$ に反する。よって主張が成り立つ。

結論. 各 $i \in {1, \dots, k}$ について、主張で得られる頂点を $x_{i} \in V_{i}$ とする。 $x_{i}$ は $i$ 以外の $k - 1$ 個の色 $j$ それぞれについて $V_{j}$ の頂点と隣接し、 $V_{j}$ たちは互いに交わらないので、これらの隣接頂点はすべて相異なる。よって $de g x_{i} \geq k - 1$ である。また $V_{1}, \dots, V_{k}$ は互いに交わらないので、 $x_{1}, \dots, x_{k}$ は相異なる $k$ 個の頂点である。

以上より、 $G$ には $de g v \geq k - 1$ を満たす頂点が少なくとも $k$ 個存在する。 $■$

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる