グラフ理論に関する諸定理の証明
4 年 B 組 松川 賢太朗
指導教員 川口 慎二

１．要約
サイエンス研究会数学班 4 年生はグラフ理論について研究している。今回はグラフ理論に関する様々な定理の証明を行うことを目標とした。
キーワード

グラフ理論、ラムゼーの定理、握手の定理、五色定理

２．研究の背景と目的
昨年から、私は組合せや確率について研完全グラフ」と「頂点数 B の青い完全グラフ」が必ず存在する。

究している。グラフ理論は組合せ問題を簡潔に見やすくしてくれる道具の 1 つである。

ここで、定理1の条件を満たす最小の頂点そのため、今回グラフ理論についての研究

数 n のことをラムゼー数といい、 R ( A, B )を行った。と表す。

３．研究内容例題 1

はじめに、グラフとは幾つかの点と、26 人の人物がいる場合、互いに知り合い点をつなぐ線分からなる図形を意味する。

である 3 人組か、互いに知らない 3 人組が各点のことを頂点、2 点を結んだ線分のこ必ず存在することを証明せよ。とを辺と呼ぶ。また、頂点 v に接続する辺の数を頂点の次数（degree）といい、 d (v )(証明)とかく。

この問題の状況をグラフ化すると図１のようになる。

３．１ ラムゼーの定理

Aすべての頂点の間に辺が存在するグラフ

Bのことを完全グラフという。完全グラフについては、次の定理が知られている。

C定理 1 (ラムゼーの定理)

D

A, B は任意の定数とする。頂点の数が n

図１の完全グラフの辺を赤と青に塗り分けると互いに知り合いである人同士を実線で、き、 n が十分大きければ「頂点数 A の赤い互いに知らない人を点線で結ぶ。つまり実線の三角形か、点線の三角形かどちらかができればいい。まず 1 点に注目する。

例題 1 と同様に考えて、実線の三角形か、点線の三角形のどちらかができればよい。

今回の場合は A とする。A からは 5 本のまず 1 点 A に注目する。A からは 7 本の辺辺が出ることになる。実線と点線で分けるが出ることになる。実線と点線で分けるたためどちらかが必ず 3 本以上である。いま、め、どちらかが必ず 3 本以上である。いま、AB, AC, AD が実線であるとすると、A, B,AB, AC, AD, AE が実線であるとする。

C, D を頂点とする三角形が考えられる。
① BC が実線のとき

このとき、A, B, C, D, E を頂点とする三角形が考えられる。

△ABC が実線の三角形である。
② CD が実線のとき① BC が実線のとき△ABC が実線の三角形である。

△ACD が実線の三角形である。
③ BD が実線のとき② CD が実線のとき△ACD が実線の三角形である。

△ABD が実線の三角形である。
④ ①～③以外のとき③ DE が実線のとき△ABD が実線の三角形である。

BC, CD, BD はすべて点線なので、△BCD が点線の三角形である。
いずれにせよ、実線の三角形か、点線の(Q. E. D.)三角形かどちらかができる。

④ BD が実線のとき△ABD が実線の三角形である。
⑤ BE が実線のとき△ABE が実線の三角形である。
⑥ CE が実線のとき

例題 2△ACE が実線の三角形である。

8 人の人物がいる場合、互いに知り合いである 3 人組か、互いに知らない 3 人組が必ず存在することを証明せよ。

⑦ BC, CD, BD が点線のとき△BCD が点線の三角形である。
⑧ BC, CE, BE が点線のとき△BCE が点線の三角形である。
⑨ CD, DE, CE が点線のとき

証明
この問題をグラフ化すると図２のように△CDE が点線の三角形である。
⑩ BD, DE, BE が点線のときなる。
A△BCD が点線の三角形である。

B

いずれにせよ、実線の三角形か、点線のC三角形かどちらかができる。

D３．２ 握手の定理(Q. E. D.)

グラフの次数について、次の定理が知らE
図２れている。

定理 2 (握手の定理)

合計は 2k となる。 (Q. E. D.)

任意のグラフにおいて、各頂点の次数の総和は辺の本数の 2 倍に等しい。

(証明 2)
接続行列の各列の総数はその辺と接続しこの定理を証明する前に接続行列についている頂点の次数の総数である。よって接続行列の 1 の総数は全頂点の次数の和であて説明しておく。

る。各列の次数の和は必ず 2 なので、グラ1eフの辺の本数を k 本とすると全頂点の次数5の合計は 2k となる。 (Q. E. D.)

ad３．３ 五色定理
42bc3

グラフ理論の応用として、地図の塗り分け問題が挙げられる。地図の塗り分けについては、次の「五色定理」がある。

図３
図３のようなグラフ G について考える。
頂点 n 個、辺 m 本のグラフに対する接続行列は n  m 行列である。各行は頂点、各列

定理 3 (五色定理)
どのような地図でも五色あれば塗り分けることができる。

は辺に対応している。 p 番目の頂点と q 番目の辺が接続しているとき、接続行列のこの五色定理を、グラフ理論を用いて証( p, q ) 成分は 1 であり、接続していないとき、 ( p, q ) 成分は 0 である。下の行列は図明しよう。まず、次の補題を準備する。n 色３のグラフ G に対する接続行列である。

異なる色になるように頂点を塗ることがでを用意すれば、グラフのどの辺の両端点もきるとき、このグラフは n 彩色可能である

a b c d e123451100001100001100001110001 という。
命題
平面グラフは 5 彩色可能である。
(証明)
数学的帰納法で示す。平面グラフ G の頂(証明 1)
頂点 u と v をつないだとき、 u の次数は＋1 されて、v の次数も＋1 される。
つまり、辺 1 本につき次数は＋2 になる。グラフの辺の本数を k 本とすると、全頂点の次数の点の数、辺の数、面の数をそれぞれ、V , E ,F とする。

V  1のときは自明である。V  k のとき5 彩色可能であると仮定し、 V  k  1 のとき、G が 5 彩色可能であることを証明する。

まず、次の補題から証明する。とがわかる。平均以下の次数は必ず存在し、次数は整数であることから、平面グラフには次数 5 以下の頂点が必ず存在する。

補題
平面グラフには、次数 5 以下の頂点が必(Q. E. D.)ず存在する。
(定理 3 の証明)
(補題の証明 1)

頂点数 5 以下の平面グラフについて命題

平面グラフのすべての頂点の次数が 6 以が成り立つことは自明である。頂点数 k 以上であると仮定する。またグラフは連結し下のすべての平面グラフに対して五色定理ていると仮定する。それぞれの頂点に辺がが成り立っていると仮定する。 k  1 個の頂6 本以上連結しているので、点をもつ任意の平面グラフを G として、G6V ≦ 2E …① となる。

E  1 のときは自明である。以下は辺のが 5 彩色可能であることを示す。

2E03G には、補題より次数 5 以下の頂点が存在する。 G の最小次数の頂点を v とする。
このとき、 d (v ) ≦ 5 となる。 G から v とそれに接続する辺を除いたグラフを G とする。 G は頂点数 k の平面グラフなので、仮定より G は 5 彩色可能である。
d (v ) ≦ 4 のとき、 v と接続している頂点となるが、オイラーの多面体定理より、(左を塗り分ける色の数は 4 以下なので v は残辺)＝2 であり矛盾する。よって背理法より、った色で塗ることができる。

数が 2 以上のものだとする。それぞれの面は 3 本以上の辺を境界としてもち、1 本の辺は 2 つの面の境界になり得るため、3F ≦ 2E …②
13①，②より、V  E  F ≦ E  E 

補題は証明された。 (Q. E. D.)d (v )  5 のとき、 v に接続している頂点を塗り分けている色の数が 4 以下なら v は(補題の証明 2)残った色で塗ることができる。

上述の補題の証明 1 より、 3F ≦ 2E …

d (v )  5 であり、 v に接続している頂点(*) は成り立つ。また、オイラーの多面体定を塗り分けている色が 5 色であるの場合(図理より、 V  F  E  2 …(†)

４参照)を考える。

(*)，(†)から3V ≧ E  6 …(‡)
が得られる。また、各頂点の次数の総和を Dと置くと、握手の定理(定理 2)より、D  2Eを(‡)に代入して、vD 6 ≦ 3V2となるので、 D ≦ 6  12  6 ．
VV
これより、次数の平均が 6 未満であるこ

図４

このとき、2 パターンの場合が考えられる。5 つの頂点を v1 , v2 , v3 , v4 , v5 とおく。

v1 と v3 を結ぶ辺と頂点の集合は存在す

また、 v1 , v2 , v3 , v4 , v5 の各頂のそれぞれる。一方、グラフ G は平面グラフなので、v 2に、c1 , c2 , c3 , c4 , c5 の色を塗るとする。さと v 4 を結ぶ辺と頂点の集合は存在しない。

らに、 v1 から c1 と c3 を交互に塗っていた頂

この場合は［パターン１］と同様に考える。
ここで v 2 から c 2 と c 4 を交互に頂点を塗っ~点の集合を V とする。ていった頂点の集合を V̂ とする。
［パターン１］~v3 が V に含まれていない場合

v1v5

v1v5v2v4v2vV̂

v~
Vv3v4

図７v3
図５~

この場合、V の中の c1 と c3 の色を交換すれば条件を変えずに v1 , v2 , v3 , v4 , v5 を 4 色で塗り分けることができる。よって、残った色 c1 で v を塗ることができる。

このとき、V̂ の中の c 2 と c 4 の色を交換す
れば条件を変えずに v1 , v2 , v3 , v4 , v5 を 4 色で塗り分けることができる。よって、残った色 c 2 を v に塗ることができる。
これらより平面グラフは 5 彩色可能とわかる。 (Q. E. D.)［パターン 2］~v 3 が V に含まれている場合

３．４ 道色分け問題
グラフ理論の応用例として、「道色分け問題」という以下の問題がある。

v1「道色分け問題」とは、例えば図８のよv5v2v

うな黄色がゴール地点とする地図があるとする。このとき、スタート地点がどの場所であっても青－赤－赤－青－赤－赤という

v4v3
図６

順に進めば必ず黄色のゴール地点に到着できることを示せ(ただし、途中でゴールに到着してもよい)という問題である。

⑤F の場合
F－E－A－B (青－赤－赤)⑥ G の場合
G－C－F－B (青－赤－赤)⑦ H の場合
H－A－B (青－赤)以上のように、ゴール地点を B にしたとき、どこをスタート地点にしても青－赤－赤の順に進めばゴール地点に到着すること図８がわかる。

いくつかの例を試してみる。まず、このグラフの頂点を下図のようにする。

４．今後の展望
今回の研究でグラフ理論を利用することで彩色問題のような問題を今までとは違った方向から考えられることがわかった。今回、五彩色問題の証明を行ったので次回はグラフ理論を利用して四色問題を考えてみようと思う。このとき「平面グラフには次数 4 以下の頂点が必ず存在する」ということを証明すればよい。そしてすべての頂点の次数が 5 以上のグラフを発見できるのか

図９についても探究してみたい。また、道色分

今回のゴール地点を B として、スタートけ問題の証明にも再挑戦しようと思う。

地点によって場合分けをする。
① A の場合

５．参考文献A－D－H－G－C－F－B[1] 「グラフ理論入門—基本とアルゴリズ(青－赤－赤－青－赤－赤)ム」、宮崎修一、森山出版(2015)② C の場合[2] 「高校数学の美しい物語」

C－D－H－G－C－F－B

http://mathtrain.jp(青－赤－赤－青－赤－赤)[3] 「Wolfram Math World」③ D の場合
D－G－F－B (青－赤－赤)

http://mathworld.wolfram.com/RoadColoringProblem.html④ E の場合E－H－G－F－E－A－B(青－赤－赤－青－赤－赤)６．謝辞
今回の研究にあたり、ご指導下さいまし
た顧問の川口先生ありがとうございました。