美術館定理

同義語：美術館問題art gallery theorem

概要

前提知識: 多角形のJordan曲線定理, 多角形の内角の和と外角の和, 鳩の巣原理, 数学的帰納法と整列性

高校での出発点：何人の警備員で見張れるか

壁がまっすぐな $n$ 枚の板でできた美術館の部屋がある。部屋の中に警備員を立たせ、部屋のどの場所も少なくとも 1 人の警備員から見えるようにしたい。警備員はその場で 1 周見回せるが、壁の向こうは見えない。何人いれば足りるだろうか。
部屋が凸な形なら 1 人で足りる。部屋がへこんでいると 1 人では足りないことがある。まず小さな例で確かめる。

C の字の部屋

多角形のJordan曲線定理の例で使った C の字の 8 角形を部屋にする。頂点は順に
$$ P_1(0,0),\ P_2(6,0),\ P_3(6,5),\ P_4(0,5),\ P_5(0,4),\ P_6(5,4),\ P_7(5,1),\ P_8(0,1) $$
である。部屋は、上の腕（$0\le x\le6$、$4\le y\le5$ の長方形）、右の柱（$5\le x\le6$、$0\le y\le5$）、下の腕（$0\le x\le6$、$0\le y\le1$）を合わせたもので、左の口（$0< x<5$、$1< y<4$）は部屋の外である。
(1) 1 人では足りない。上の腕の左端の点 $A\left(0,\dfrac92\right)$ と下の腕の左端の点 $B\left(0,\dfrac12\right)$ を考える。点 $Z(x,y)$ から $A$ が見えるとし、$y<4$ と仮定する。$Z$ が $x\le5$ の範囲にあれば、$Z$ は下の腕の点（$y\le1$）か、壁 $P_6P_7$ の上の点（$x=5$、$1< y<4$）である。下の腕の点なら、線分 $AZ$ は高さ $\dfrac52$ の点を $x<5$ の範囲で通る。その点は、高さが合わないので上の腕にも下の腕にもなく、$x<5$ なので右の柱にもなく、部屋の外にある。壁 $P_6P_7$ の上の点なら、線分 $AZ$ の $Z$ のすぐ手前の点は $x<5$、$1< y<4$ を満たすので口の中にあり、部屋の外にある。したがって $5< x\le6$ である。このとき線分 $AZ$ は、$x=5$ の壁 $P_6P_7$ より上（高さ $4$ 以上）を通る必要がある。高さ $1$ と $4$ の間で $x=5$ を通ると、そのすぐ左で口に入り、高さ $1$ 以下で通ると、その先で高さ $\dfrac52$ の点を $x<5$ で通るからである。線分 $AZ$ の $x=5$ での高さは $\dfrac92+(y-\dfrac92)\cdot\dfrac5x$ で、これが $4$ 以上であることから
$$ \left(\frac92-y\right)\cdot\frac5x\le\frac12,\qquad y\ge\frac92-\frac x{10}\ge\frac92-\frac6{10}=\frac{39}{10} $$
である。よって $A$ が見える点はすべて $y\ge\dfrac{39}{10}$ を満たす。上下を入れかえた同じ計算で、$B$ が見える点はすべて $y\le\dfrac{11}{10}$ を満たす。両方を満たす点はないので、$A$ と $B$ を 1 人で見ることはできない（図 1）。
(2) 2 人で足りる。$P_3(6,5)$ に 1 人、$P_7(5,1)$ に 1 人を置く。上の腕と右の柱はどちらも長方形で $P_3$ を含むので、$P_3$ からその中の点を結ぶ線分は長方形の中にあり、全部見える。下の腕は長方形で $P_7$ を含むので、$P_7$ から全部見える。3 つを合わせると部屋全体である。

C の字の部屋。青は点 A が見える範囲、橙は点 B が見える範囲で、重なりがない
C の字の部屋は壁が $8$ 枚で、$2$ 人が必要かつ十分だった。$8$ を $3$ で割ると $2$ 余り $2$ である。この記事の主定理は、壁が $n$ 枚の部屋はいつも $\left\lfloor\dfrac n3\right\rfloor$ 人で見張れ、それより少なくては見張れない部屋もある、というものである（$\lfloor t\rfloor$ は $t$ 以下の最大の整数）。この記事では次の問いに答える。

$\left\lfloor\dfrac n3\right\rfloor$ 人でいつも足りるのはなぜか。どこに立たせればよいか。→ thm-agt-main (1)、lem-agt-triangulation、lem-agt-color

$\left\lfloor\dfrac n3\right\rfloor$ 人が本当に必要な部屋はあるか。→ thm-agt-main (2)、ex-agt-comb

高校での見方	この記事の言葉	大学の言葉
部屋を三角形に切り分ける	三角形分割	多角形の三角形分割、平面グラフ
頂点を 3 色で塗る	どの三角形も 3 色がそろう塗り分け	グラフの 3 彩色
いちばん少ない色を選ぶ	$\left\lfloor\frac n3\right\rfloor$ 個以下の頂点	鳩の巣原理
櫛の形の部屋	$\left\lfloor\frac n3\right\rfloor$ 人が必要な例	下からの評価

言葉の準備：美術館と「見える」

美術館と見張り

$n\ge3$ とし、$P$ を $n$ 個の頂点をもつ単純多角形とする（多角形のJordan曲線定理の単純多角形）。$P$ の周と内部を合わせた図形を $\mathcal G$ と書き、美術館 と呼ぶ。
$\mathcal G$ の 2 点 $G$、$X$ について、線分 $GX$ が $\mathcal G$ に含まれるとき、$G$ から $X$ が 見える という。線分が壁（周）に触れたり、壁に沿ったりしてもよい。$\mathcal G$ の有限個の点 $G_1,\dots,G_k$（警備員）が $\mathcal G$ を 見張る とは、$\mathcal G$ のどの点 $X$ も、少なくとも 1 人の $G_i$ から見えることをいう。

「見える」は、線分が美術館からはみ出さないことである。美術館の外（多角形のJordan曲線定理の外部）の点を通る線分は見えない。

凸多角形は 1 人で見張れる

正六角形の美術館では、どの 1 点に警備員を置いても全体が見える。凸多角形の周と内部を合わせた図形は、中の 2 点を結ぶ線分を含むからである（内角がすべて $180^\circ$ 未満の多角形は、各辺を含む直線に関して内部と同じ側にある点の集まりの共通部分であり、そのような集まりはどれも中の 2 点を結ぶ線分を含む。この記事ではこの事実を証明せずに使う。凸な図形については点の存在範囲と凸結合）。
凸でない美術館でも 1 人で足りることがある。矢じり形の四角形 $(0,0)$、$(2,1)$、$(4,0)$、$(2,3)$ では、頂点 $(2,3)$ から全体が見える。この四角形は、三角形 $(0,0),(2,1),(2,3)$ と三角形 $(2,1),(4,0),(2,3)$ を合わせたもので、$(2,3)$ はどちらの三角形の頂点でもあり、三角形の中の点はその頂点から見えるからである。

主定理：$\left\lfloor\frac n3\right\rfloor$ 人で足り、それより少なくては足りない部屋がある

美術館定理

$n\ge3$ とする。
(1) $n$ 個の頂点をもつどの美術館も、$\left\lfloor\dfrac n3\right\rfloor$ 人以下の警備員で見張れる。しかも警備員は頂点に置ける。
(2) 各 $n\ge3$ について、$\left\lfloor\dfrac n3\right\rfloor$ 人より少ない警備員では見張れない、$n$ 個の頂点をもつ美術館がある。

の証明は、部屋を三角形に切り分け、頂点を 3 色で塗り分けるという 2 つの準備からなる。

準備 1：三角形分割

単純多角形の、隣り合わない 2 つの頂点を結ぶ線分で、両端以外で周と交わらず内部を通るものを 対角線 という。$n\ge4$ の単純多角形には対角線があることは、多角形の内角の和と外角の和の補題「対角線の存在」で、左端の頂点を使って証明されている（靴ひも公式にも同じ補題がある）。また、対角線 $P_iP_j$（$i< j$）は多角形を 2 つの単純多角形 $P_iP_{i+1}\cdots P_j$ と $P_jP_{j+1}\cdots P_nP_1\cdots P_i$ に分け、2 つの内部を合わせるともとの内部から対角線を除いたものになる。この「分ける」性質は多角形の内角の和と外角の和の (J2) で、この記事でも証明せずに使う（多角形のJordan曲線定理では扱っていない）。

三角形分割

美術館 $\mathcal G$ を、互いに交わらない（端の点を除いて共有点をもたない）何本かの対角線で切り分け、切り分けた部分がすべて三角形になるとき、その切り分け方を $\mathcal G$ の 三角形分割 という。三角形の頂点はどれも多角形の頂点である。

三角形分割の存在

$n\ge3$ 個の頂点をもつ単純多角形には三角形分割があり、どの三角形分割も $n-3$ 本の対角線と $n-2$ 個の三角形からなる。

対角線で 2 つに分けて帰納法

方針：$n$ についての数学的帰納法で示す。「$n$ より小さいすべての場合に正しい」と仮定する形の帰納法を使う（数学的帰納法と整列性）。
段 1（$n=3$）。三角形そのものが三角形分割で、対角線は $0=3-3$ 本、三角形は $1=3-2$ 個である。三角形には対角線がないので、三角形分割はこれだけである。
段 2（存在）。$n\ge4$ とし、頂点が $n$ 個より少ない単純多角形では正しいと仮定する。対角線 $P_iP_j$（$i< j$）が 1 本ある。これで多角形は、頂点が $k=j-i+1$ 個の多角形 $Q_1$ と、$n-k+2$ 個の多角形 $Q_2$ に分かれる。$P_i$ と $P_j$ は隣り合わないので $k\ge3$、$n-k+2\ge3$ で、$k\le n-1$ かつ $n-k+2\le n-1$ である。帰納法の仮定により $Q_1$、$Q_2$ には三角形分割があり、その対角線に $P_iP_j$ を加えると、もとの多角形の三角形分割になる（$Q_1$、$Q_2$ の対角線はそれぞれの内部を通るので、互いに交わらず、$P_iP_j$ とも交わらない）。
段 3（本数と個数）。どの三角形分割でも、$n\ge4$ なら対角線は少なくとも 1 本ある（1 本もなければ多角形そのものが三角形で、$n=3$ になる）。その 1 本 $P_iP_j$ で段 2 のように $Q_1$、$Q_2$ に分けると、残りの対角線と三角形はどれも $Q_1$ か $Q_2$ の一方に入り（対角線どうしは交わらないので $P_iP_j$ をまたがない）、それぞれの三角形分割になる。帰納法の仮定により、三角形は
$$ (k-2)+\bigl((n-k+2)-2\bigr)=n-2 $$
個、対角線は $P_iP_j$ を加えて
$$ (k-3)+\bigl((n-k+2)-3\bigr)+1=n-3 $$
本である。$\square$

多角形が三角形に分けられることは、BTB11 も Problem 25（4 頂点以上の多角形は、内部を通る線分で 2 つに分けられる）と Problem 28（分け方をくり返して三角形分割する）で、読者への問題として扱っている。三角形の個数 $n-2$ から、内角の和が $(n-2)\times180^\circ$ であることもすぐに分かる（多角形の内角の和と外角の和）。

C の字の部屋を三角形に分ける

ex-agt-start の 8 角形を、5 本の対角線 $P_1P_7$、$P_2P_7$、$P_2P_6$、$P_3P_6$、$P_3P_5$ で切り分けると、6 個の三角形
$$ P_1P_2P_7,\quad P_1P_7P_8,\quad P_2P_6P_7,\quad P_2P_3P_6,\quad P_3P_5P_6,\quad P_3P_4P_5 $$
になる（図 2）。$n=8$ で、対角線は $8-3=5$ 本、三角形は $8-2=6$ 個である。下の 2 つは下の腕、真ん中の 2 つは右の柱、上の 2 つは上の腕に入っている。面積は順に $3,\ \dfrac52,\ \dfrac32,\ \dfrac52,\ \dfrac52,\ 3$ で、和は $15$、8 角形の面積 $30-15=15$（$6\times5$ の長方形から口の $5\times3$ を除く）と一致する。

準備 2：頂点の 3 色の塗り分け

三角形分割の頂点は 3 色で塗り分けられる

単純多角形の三角形分割が 1 つ与えられたとき、多角形の頂点を 3 色で塗って、どの三角形の 3 頂点も互いに違う色になるようにできる。

対角線の両側を塗って色の名前をそろえる

方針：頂点の個数 $n$ についての数学的帰納法で示す。対角線で 2 つに分け、両側を別々に塗ってから、対角線の両端の色が合うように片側の色の名前をつけかえる。
段 1（$n=3$）。三角形 1 つなので、3 頂点を 3 色で塗ればよい。
段 2（分ける）。$n\ge4$ とし、頂点が $n$ 個より少ない場合は正しいと仮定する。三角形分割には対角線 $d=P_iP_j$ があり、lem-agt-triangulation の証明の段 3 のように、$d$ で多角形を $Q_1$、$Q_2$ に分けると、三角形分割も $Q_1$ の三角形分割と $Q_2$ の三角形分割に分かれる。帰納法の仮定により、$Q_1$ の頂点を色 $1,2,3$ で、どの三角形も 3 色になるように塗れる。$Q_2$ の頂点も同じように塗れる。
段 3（色の名前をつけかえる）。$d$ は $Q_1$ の辺なので、$Q_1$ のある三角形の辺であり、その三角形は 3 色なので $P_i$ と $P_j$ は違う色である。$Q_1$ での色を $P_i$ が $a$、$P_j$ が $b$ とし、残りの色を $c$ とする。$Q_2$ でも $P_i$ と $P_j$ は違う色である。$Q_2$ の塗り方の色の名前を、$P_i$ の色が $a$、$P_j$ の色が $b$、残りの色が $c$ になるようにつけかえる（3 色の名前を入れかえても、どの三角形も 3 色であることは変わらない）。
段 4（合わせる）。$P_i$、$P_j$ 以外の頂点は $Q_1$ と $Q_2$ の一方だけの頂点なので、その側の色で塗る。$P_i$、$P_j$ は両側で同じ色になった。こうして多角形の全頂点が塗られ、どの三角形も $Q_1$ か $Q_2$ の三角形なので 3 色である。$\square$

C の字の部屋を塗り分ける

ex-agt-triangulation の三角形分割で、1 つの三角形から始めて、対角線を渡りながら色を決めていく。3 色を $1,2,3$ とする（図 2 では丸・四角・三角の印）。
(1) 三角形 $P_1P_2P_7$ を $P_1=1$、$P_2=2$、$P_7=3$ と塗る。
(2) 対角線 $P_1P_7$ の向こうの三角形 $P_1P_7P_8$ では、$P_1=1$、$P_7=3$ なので $P_8=2$ に決まる。
(3) 対角線 $P_2P_7$ の向こうの三角形 $P_2P_6P_7$ では、$P_2=2$、$P_7=3$ なので $P_6=1$ である。続けて三角形 $P_2P_3P_6$ で $P_3=3$、三角形 $P_3P_5P_6$ で $P_5=2$、三角形 $P_3P_4P_5$ で $P_4=1$ である。
色ごとに数えると、色 $1$ が $P_1,P_4,P_6$ の 3 個、色 $2$ が $P_2,P_5,P_8$ の 3 個、色 $3$ が $P_3,P_7$ の 2 個である。いちばん少ない色 $3$ の頂点 $P_3$、$P_7$ は、ex-agt-start (2) で置いた 2 人の位置と同じである。

C の字の部屋の三角形分割と 3 色の塗り分け。破線が対角線、丸で囲んだ 2 つの三角の印の頂点に警備員を置く

櫛の形の 9 角形の三角形分割と 3 色の塗り分け。太い線の対角線 Q1Q5 で左右 2 つの多角形に分かれる

1 つ目の三角形の色を決めると、あとの色は対角線を渡るたびに 1 通りに決まった。途中で矛盾が起きないのは、lem-agt-color の証明のとおり、対角線で切ると多角形が 2 つに分かれ、同じ頂点に別の道筋から戻ってくることがないからである。

主定理の証明

塗り分けと櫛の形

方針：(1) は、三角形分割の頂点を 3 色で塗り、いちばん少ない色の頂点に警備員を置く。(2) は、細い歯が $k$ 本ある櫛の形の部屋を作り、歯の先を見られる場所が歯ごとに離れていることを示す。
段 1（(1)：塗る）。lem-agt-triangulation により美術館 $\mathcal G$ の三角形分割をとり、lem-agt-color により頂点を色 $1,2,3$ で、どの三角形も 3 色になるように塗る。
段 2（(1)：いちばん少ない色）。色 $1,2,3$ の頂点の個数を $a,b,c$ とすると $a+b+c=n$ である。3 つとも $\dfrac n3$ より大きいとすると $a+b+c>n$ となり矛盾するので、どれか 1 つ、たとえば $a$ は $\dfrac n3$ 以下である（鳩の巣原理の考え方）。$a$ は整数なので $a\le\left\lfloor\dfrac n3\right\rfloor$ である。
段 3（(1)：置いて見張る）。色 $1$ の $a$ 個の頂点すべてに警備員を置く。三角形分割のどの三角形も 3 頂点が 3 色なので、色 $1$ の頂点をちょうど 1 つもち、そこに警備員がいる。三角形は $\mathcal G$ に含まれ、中の 2 点を結ぶ線分を含むので、その警備員から三角形全体が見える。$\mathcal G$ のどの点もどれかの三角形に入るので、$a$ 人の警備員が $\mathcal G$ を見張る。人数を $\left\lfloor\dfrac n3\right\rfloor$ にそろえたければ、残りの人を好きな頂点に置けばよい。
段 4（(2)：櫛の形）。$k\ge1$ とし、$T_j=(4j-2,\,6)$（$j=1,\dots,k$）とおく。次の $3k$ 個の点をこの順に結んだ多角形を櫛形 $K_k$ とする。
$$ (0,0),\ (4k,0),\ T_k,\ (4k-3,1),\ (4k-5,1),\ T_{k-1},\ (4k-7,1),\ (4k-9,1),\ \dots,\ T_2,\ (5,1),\ (3,1),\ T_1 $$
$T_j$ が $j$ 本目の歯の先で、歯と歯の間は高さ $1$ の谷になっている（図 4 は $k=4$）。$K_k$ の頂点は $2+k+2(k-1)=3k$ 個である。$n=3k+1$ のときは $(0,0)$ と $(4k,0)$ の間に点 $(2k,-1)$ を、$n=3k+2$ のときは点 $\left(\dfrac{4k}3,-1\right)$、$\left(\dfrac{8k}3,-1\right)$ を加えて、底を少し下にふくらませる。どの場合も $\left\lfloor\dfrac n3\right\rfloor=k$ で、部屋の点の高さ $y$ は $-1\le y\le6$ である。
段 5（(2)：歯の先を見られる場所）。歯の先 $T_j$ での 2 本の辺の向きを $\vec u$（左下へ）、$\vec v$（右下へ）とし、$T_j+s\vec u+t\vec v$（$s,t\ge0$）の形の点の集まりを $W_j$ とする。$W_j$ は、$T_j$ から 2 本の辺を下へ延ばした直線ではさまれた、下向きに開いたくさび形である。$T_j$ のすぐ近くでは、部屋は 2 本の辺ではさまれた角の部分だけなので、$T_j$ が見える点 $G$ について線分 $T_jG$ は $T_j$ を出るときにこの角の中へ向かう。したがって $G$ は $W_j$ に入る。
段 6（(2)：くさびは重ならない）。$2\le j\le k-1$ の歯の 2 本の辺は、$T_j$ から $(4j-3,1)$、$(4j-1,1)$ へ向かい、傾きの大きさは $5$ である。高さ $y$（$y\le6$）での $W_j$ の右の境は $x=4j-2+\dfrac{6-y}5$ で、これは $j=1$ でも同じである。$W_{j+1}$ の左の境は $x=4(j+1)-2-\dfrac{6-y}5=4j+2-\dfrac{6-y}5$ で、これは $j+1=k$ でも同じである。2 つの差は
$$ \left(4j+2-\frac{6-y}5\right)-\left(4j-2+\frac{6-y}5\right)=4-\frac{2(6-y)}5 $$
で、$y>-4$ なら正である。部屋の点は $y\ge-1$ なので、部屋の中では $W_j$ は $W_{j+1}$ より左にあり、$W_{j+1},W_{j+2},\dots$ はさらに右にある。よって部屋の中で 2 つのくさびが重なることはない。
段 7（(2)：まとめ）。段 5・段 6 により、1 人の警備員から見える歯の先は高々 1 つである。$k$ 個の歯の先をすべて見るには $k=\left\lfloor\dfrac n3\right\rfloor$ 人以上が必要である。$\square$

櫛の形の 12 角形。4 つの歯の先（黒い点）が見える場所は色をつけたくさび形で、互いに重ならない。星の位置の 4 人で全体を見張れる

櫛形の 9 角形

$k=3$ の櫛形 $K_3$ の頂点を順に
$$ Q_1(0,0),\ Q_2(12,0),\ Q_3(10,6),\ Q_4(9,1),\ Q_5(7,1),\ Q_6(6,6),\ Q_7(5,1),\ Q_8(3,1),\ Q_9(2,6) $$
とする。歯の先は $Q_9$、$Q_6$、$Q_3$ である。
(1) 3 人が必要。高さ $0$ でのくさびの幅は、$W_1$ が $0\le x\le\dfrac{16}5$、$W_2$ が $\dfrac{24}5\le x\le\dfrac{36}5$、$W_3$ が $\dfrac{44}5\le x\le12$ で、互いに離れている。
(2) 3 人で足りる。7 個の三角形 $Q_1Q_8Q_9$、$Q_5Q_6Q_7$、$Q_2Q_3Q_4$、$Q_1Q_7Q_8$、$Q_1Q_5Q_7$、$Q_1Q_4Q_5$、$Q_1Q_2Q_4$ で三角形分割する（図 3、$9-2=7$ 個）。対角線 $Q_1Q_5$ で、左の 6 角形 $Q_5Q_6Q_7Q_8Q_9Q_1$ と右の 5 角形 $Q_1Q_2Q_3Q_4Q_5$ に分かれる。左を $Q_1=1$、$Q_8=2$、$Q_9=3$、$Q_7=3$、$Q_5=2$、$Q_6=1$ と塗る。右を別に $Q_1=2$、$Q_5=3$、$Q_4=1$、$Q_2=3$、$Q_3=2$ と塗ったとすると、$Q_1$、$Q_5$ の色を左に合わせるために名前を $2\to1$、$3\to2$、$1\to3$ とつけかえて、$Q_4=3$、$Q_2=2$、$Q_3=1$ になる。色 $1$ は $Q_1,Q_3,Q_6$ の 3 個で、ここに 3 人を置けば見張れる。

の「右を別に塗った」ときの色は、lem-agt-color の証明の段 3 のつけかえを具体的に見せるための一例である。右の 5 角形の 3 つの三角形 $Q_1Q_4Q_5$、$Q_1Q_2Q_4$、$Q_2Q_3Q_4$ はどれも、つけかえの前後で 3 色になっている。

頂点の数 $n$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$12$
凸多角形に必要な人数	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
櫛形（底をふくらませたものを含む）に必要な人数	$1$	$1$	$1$	$2$	$2$	$2$	$3$	$4$
どの美術館でも足りる人数 $\left\lfloor\frac n3\right\rfloor$	$1$	$1$	$1$	$2$	$2$	$2$	$3$	$4$

C の字の部屋（$n=8$）は 2 人が必要で、櫛形と同じく $\left\lfloor\dfrac n3\right\rfloor$ 人が必要な例になっている。

凸多角形

凸多角形の美術館は、どの頂点に置いた 1 人の警備員でも見張れる。

ex-agt-convex (1) の事実（凸多角形は中の 2 点を結ぶ線分を含む）から、どの点に置いても全体が見える。$n$ が大きくても $\left\lfloor\dfrac n3\right\rfloor$ 人は要らず、thm-agt-main (1) の人数はあくまで「どの形でも足りる」上限である。凸多角形の三角形分割が何通りあるかは、Catalan数（高校数学）で数える。

例と反例

lem-agt-color、thm-agt-main、cor-agt-convex の条件を 1 つずつ外す。

外す条件	反例	成り立たなくなること
色の数が $3$	三角形 1 つを $2$ 色で塗る	どの三角形も 3 頂点が違う色になる
人数が $\left\lfloor\frac n3\right\rfloor$	櫛形の 9 角形に $2$ 人	全体を見張れる
多角形が凸	櫛形の 6 角形	1 人で見張れる

反例：2 色では塗り分けられない

三角形の 3 頂点を 2 色で塗ると、鳩の巣原理により 2 頂点が同じ色になる。したがって、どの三角形分割でも「どの三角形も 3 頂点が違う色」の塗り分けは 2 色ではできない。lem-agt-color の色の数 $3$ は減らせない。色が $3$ 個あるから、thm-agt-main の証明の段 2 で「いちばん少ない色は $\frac n3$ 以下」が出る。

反例：人数を 1 人減らす

ex-agt-comb の櫛形の 9 角形は $\left\lfloor\dfrac93\right\rfloor=3$ 人で見張れるが、$2$ 人では見張れない。3 つのくさび $W_1$、$W_2$、$W_3$ は重ならないので、2 人ではどれかのくさびに誰もいない。そのくさびの歯の先は誰からも見えない。

反例：凸でない部屋

$k=2$ の櫛形 $K_2$ は、頂点 $(0,0)$、$(8,0)$、$(6,6)$、$(5,1)$、$(3,1)$、$(2,6)$ の 6 角形である。歯の先 $(2,6)$、$(6,6)$ を見られる場所は、高さ $0$ でそれぞれ $0\le x\le\dfrac{16}5$、$\dfrac{24}5\le x\le8$ のくさびの中にあり、高さ $0$ 以上では重ならない（thm-agt-main の証明の段 6）。よって 1 人では見張れず、2 人が必要である。凸という条件を外すと cor-agt-convex は成り立たない。
逆に、1 人で見張れる部屋が凸とは限らない。ex-agt-convex (2) の矢じり形は凸でないが、頂点 $(2,3)$ の 1 人で見張れる。

大学数学で見る：グラフの彩色と定理の広がり

多角形の頂点を点、辺と三角形分割の対角線を線とみると、一筆書きとグラフで扱うグラフになる。lem-agt-color は、このグラフの頂点を、線で結ばれた 2 点が違う色になるように 3 色で塗れる、つまり彩色数が $3$ であることを示している（彩色数）。平面に交わらずに描けるグラフ一般では 4 色が必要なこともあり、4 色で足りることが四色定理である（この記事では証明しない）。多角形の三角形分割のグラフは、対角線で切るたびに 2 つに分かれる特別な形をしているので、3 色で足りる。

定理の由来と、条件を変えた問題を開く

ORo87 の §1.1・§1.2 によれば、この問題は 1973 年に V. Klee が V. Chvátal に出したもので、Chvátal は 1975 年に帰納法で $\left\lfloor\frac n3\right\rfloor$ 人で足りることを示し、櫛形で必要なことも示した。この記事の三角形分割の 3 色の塗り分けによる証明は、1978 年の S. Fisk の短い証明である（Wei26 にも 2 つの論文が挙がっている）。ORo87 には、この記事で扱わない次の注意も図で示されている：3 つおきの頂点に警備員を置くだけでは見張れない部屋がある（Fig. 1.3）、壁（周）をすべて見られても内部に見えない所が残る部屋がある（Fig. 1.4）、頂点に限らず置ける 1 人で見張れるのに頂点に限ると 2 人要る部屋がある（Fig. 1.5）。

中に柱（穴）がある美術館については、壁の総数を $n$、穴の数を $h$ とすると $\left\lfloor\frac{n+h}3\right\rfloor$ 人で見張れることが証明されている（Wei26。この記事では証明しない）。穴があると lem-agt-color の証明が使えない。穴を囲むように対角線がつながると、対角線で切っても 2 つに分かれないからである。

三角形分割を実際に計算機で求める方法（計算幾何学）も ORo87 の §1.3 で扱われている。

演習

L の字の部屋

頂点が順に $L_1(0,0)$、$L_2(4,0)$、$L_3(4,2)$、$L_4(2,2)$、$L_5(2,4)$、$L_6(0,4)$ の L の字の 6 角形の部屋について答えよ。(1) 三角形分割を 1 つ作り、頂点を 3 色で塗り分けよ。(2) thm-agt-main の証明の方法では何人の警備員を置くことになるか。(3) 実際には 1 人で見張れることを示せ。

解答を開く

(1) 対角線 $L_1L_3$、$L_1L_4$、$L_4L_6$ で、4 個の三角形 $L_1L_2L_3$、$L_1L_3L_4$、$L_1L_4L_6$、$L_4L_5L_6$ に分かれる（$6-2=4$）。$L_1=1$、$L_2=2$、$L_3=3$ と塗ると、三角形 $L_1L_3L_4$ から $L_4=2$、三角形 $L_1L_4L_6$ から $L_6=3$、三角形 $L_4L_5L_6$ から $L_5=1$ に決まる。

(2) 色 $1$ は $L_1,L_5$、色 $2$ は $L_2,L_4$、色 $3$ は $L_3,L_6$ で、どの色も 2 個である。証明の方法では $2=\left\lfloor\frac63\right\rfloor$ 人を置く（たとえば $L_1$ と $L_5$）。

(3) 部屋は長方形 $0\le x\le4$、$0\le y\le2$ と長方形 $0\le x\le2$、$0\le y\le4$ を合わせたもので、$L_1(0,0)$ はどちらの長方形にも入っている。長方形は中の 2 点を結ぶ線分を含むので、$L_1$ からどちらの長方形の点も見える。よって $L_1$ の 1 人で見張れる。thm-agt-main (1) の人数は上限で、部屋によってはもっと少なくて済む。

さらに先へ

次に読む Erdős–Szekeresの定理（凸多角形）では、平面に散らばった点の中から凸多角形の頂点になる点を選び出す。この記事と同じく、場合分けと帰納法と鳩の巣原理で証明する。
塗り分けの補題は、グラフの彩色（彩色数、四色定理）の最も易しい場合の一つである。
三角形分割は、多角形の面積（靴ひも公式、Pickの定理）や内角の和（多角形の内角の和と外角の和）の証明でも使われる。