Page 1 of 26
GEN025 2012 Day 26
Quiz 8: Not yet.
(Re-/Late) submission of Quiz 8 will be ac- cepted at the Final on Friday, March 1.
Paper: Pick up at H113
# of Votes Cast + Votes + Format = Total.
Votes = min(total # of votes obtained, 7)
Extra Office Hour: To be announced at the
Forum in Moodle on Saturday, February 23.
1
Page 2 of 26
Four Color Theorem
K
TK C
S
I
G
T
2
Page 3 of 26
Four Color Theorem
K
TK C
S
I
G
T
1
2 3
1
2
2
3
3
Page 4 of 26
Four Color Theorem
K
TK C
S
I
G
T
1
3 4
1
2
2
3
4
Page 5 of 26
四色定理 Kenneth Appel と Wolfgang Haken は
1970年に「平面グラフは各頂点を 4 色で塗って、同じ
色の点は隣接しないようにすることができる。」ことを証
明した。これが、四色定理 (Four Color Theorem) と
いわれるもので、どんな地図も4 色あれば隣接する国を
違う色で塗り分けることができることを示している。こ
こでは、5 色で塗ることができることを示す。∗
Theorem. 平面グラフは各頂点を 5 色で塗って、同
じ色の点は隣接しないようにすることができる。
∗同じ議論から4色では定理の条件をたもって塗り分けることができ
ないグラフで点の数が最小のものは、次数が 4 の点を含まないこ
ともわかる。
5
Page 6 of 26
Four Color Theorem A graph is said to be n- colorable if it’s possible to assign one of n colors to each
vertex in such a way that no two connected vertices have
the same color. K. Appel and W. Haken proved that every
plane graph is 4 colorable. This implies that four different
colors are sufficient to color countries on a map in such a
way that no two adjacent countries have the same color.
In the following we show a weaker result.
Theorem. Let Γ be a plane graph. Then It
is possible to assign five colors to each vertex in
such a way that no two adjacent vertices have
the same color.
6
Page 7 of 26
Proof. 1. Let Γ be a plane graph of smallest
size which is not 5-colorable.
2. Γ is connected and has a vertex x of degree
at most 5.
3. If x is removed, Γ is 5 colorable.
4. deg(x) = 5 and there is no way to color 5
vertices adjacent to x with less than 5 colors.
5. Let Γ(x) = {x1, x2, x3, x4, x5} and x1 is col- ored with 1. x2 with 2, . . . , x5 with 5.
6. There are a path with only 1 or 3 colored ver- tices from x1 to x3, and a path with only 2 or 4
colored vertices from x2 to x4. A contradiction.
7
Page 8 of 26
Regular Graphs and
Regular Polyhedra Graphs
少し美しいグラフ、極度に美しいグラフ、美しいグラフ
正則グラフと正多面体グラフと. . .
8
Page 9 of 26
k-regular graphs (k-正則グラフ)
v = 1
v = 2
v = 3
v = 4
9
Page 10 of 26
k-regular graphs (k-正則グラフ)
v = 1: k = 0
v = 2: k = 0 k = 1
v = 3: k = 0 k = 2
v = 4: k = 0 k = 1
k = 2 k = 3
10
Page 11 of 26
k-regular graphs (k-正則グラフ): v = 5
11
Page 12 of 26
k-正則グラフ: v = 5
k = 0
k = 2
k = 4
12
Page 13 of 26
k-regular graphs (k-正則グラフ): v = 6
13
Page 14 of 26
k-regular graphs (k-正則グラフ): v = 6
k = 0
k = 1
k = 2
14
Page 15 of 26
Definition. Γ = (V, E) としたとき、頂点集合 V
で辺集合は E 以外の V の二点集合 E としたものを、
Γ の補グラフ (complement of Γ) といい Γ と書く。
Γ Γ ∆ ∆
Proposition. Γ = (V, E) を 頂点の数が v の k-正
則グラフとすると Γ は 頂点の数が v の (v − k − 1)-
正則グラフである。
15
Page 16 of 26
k-regular graphs (k-正則グラフ): v = 6
k = 0 k = 5
k = 1 k = 4
k = 2 k = 3
16
Page 17 of 26
k-regular graphs (k-正則グラフ): v = 7
17