凸とは限らない領域 (美術館)に何人かの警備員を配置し，その領域全体を監視したい．
ただし，領域の境界は壁とみなし，それを通過しての監視は不可能である．「この状況で，
何人の警備員が必要か」という問題は次の定理で解決された．
定理 45 (Chv´atal, 1975) n 角形領域は n
3 人の警備員がいれば監視できる．
定理 45の n
3 は最善である．これは図 28 の例から示される．実際に，図28の多角形 領域を監視するためには，各斜線の領域に対し少なくとも 1人の警備員が必要であるが，
斜線の領域は n
3 個存在している．
図 28: 定理45 の最善の例
ここで，全頂点が外領域に隣接している平面グラフを外平面グラフと呼ぶ．
補題 46 任意の外平面グラフ G は次数が 2以下の頂点を持つ．
証明． G の内部に四角形以上の面が存在する場合は，その面に適当に対角線を引くこ とで新しい外平面グラフG′ が得られ，G′ で次数が 2以下の頂点はGでも次数は 2以下 である．したがって，Gの内部の面はすべて三角形であるとしてよい．
命題を頂点数に関する帰納法で示す．G を，内部の面がすべて三角形の外平面グラフ とする．G の頂点数は4 以上であるとしてよい．「Gの各頂点の次数が 3 以上である」と 仮定して矛盾を導く．G の頂点数を n，内部の三角形面の数を f とそれぞれおく．G は 外平面グラフであることから，外領域の境界上の辺の数は n である．
まず，各面のまわりの辺の数を数えることで，2|E(G)|= 3f+n を得る．(注：双対グ ラフの握手補題である．) また，各頂点の次数が3 以上であり内部はすべて三角形である ので，外領域の境界上の辺が属す内部の三角形はすべて異なり，したがって f ≥n であ る．よってオイラーの公式より，n+ (f + 1) =|E(G)|+ 2 であるから，
2|E(G)| = n+ 3f ≥ 2n+ 2f = 2(
|E(G)|+ 1)
となり，矛盾する．したがって，G のある頂点で次数が 2 以下である． □
系 47 任意の外平面グラフの頂点は 3 色で彩色が可能である．
証明． 外平面グラフGを考える．Gの頂点数が3以下ならば3色で彩色できることは 自明である．したがって |G| ≥4 としてよい．ここで，G からv を取り除いてできるグ ラフ G−v を考えると，G−v も外平面グラフであるため，帰納法の仮定より，T −v の 頂点は 3色で彩色できる．ここで v の近傍は高々 2頂点なのでv の近傍の頂点に使われ ていない色が存在し，v をその色で彩色すればよい． □
定理 45 の証明. ここでは，Fisk (1978)による証明を紹介する．n角形領域 Qの内部を，
新しい頂点は加えないように三角形 TQ へと分割する．(証明しないが，これは可能であ る．注：3次元の場合には 凸ではない多様体の内部を単体(正四面体)へと，新しい頂点を 追加しないように分割することは，不可能な場合が存在する．)したがって，|V(TQ)|=n であり，TQ の全頂点が外領域に接している．系47より，TQ の頂点は3色で彩色できる．
ここで，TQ の頂点数はn であるため，ある色に対し，その色で彩色されている頂点の 数は n
3 以下である．その色で彩色されているすべての頂点に警備員を配置すれば n
3 人以
下で全体を監視できる． □
演習 ∗ 以下を示せ．平面上に，1個の“穴”を持つ領域Qを考える．このQは高々⌊n+2
3
⌋ 人の警備員で監視できる．ただし，n は Qの外領域と穴に存在する壁の数の総数である．
演習 ∗ (O’Rourke, 1982) 上の演習で，穴の数が h 個のときは ⌊n+2h
3
⌋ 人の警備員で 十分であることを示せ．
予想 48 各警備員は n角形の壁に配置されその壁上を動くことができるとする．このと きは，n
4 人の警備員で十分である．
演習 ∗ 予想48 では n
4 人の警備員が必要となる美術館が存在することを示せ．
この美術館問題の亜種として，いくつかの部屋が存在する場合を考える．部屋同士は壁 によって仕切られ，警備員は壁を通過しての監視は不可能であるが，壁上に配置された警 備員はその壁の両側が監視できる，とする．また，3つ以上の壁が交わる点に配置された 警備員はその点に接するすべての部屋を監視できる．すなわち，領域の多角形がはじめか ら小領域へ分割されている場合である．この問題は刑務所の庭問題 と呼ばれている．
定理 49 (Hoffmann & Kriegel, 1996) 内部が凸四角形に分割されている領域Qはn/3 人の警備員がいれば監視できる．ただし，n は Q の頂点の数である．
補題 50 平面の三角形分割 T に対し，T の頂点が3色で彩色できるための必要十分条件 は，T の各頂点の次数が偶数であることである．
定理49 の証明. 以下は Zhang & He (2005)の証明である．定理 45の証明にならい，Q の各凸四角形面に適当に対角線を入れ，頂点が 3色で彩色できる三角形分割にできれば 良い．補題50 より，これは対角線を加え各頂点の次数が偶数である三角形分割にするこ とと同値である．(各四角形は凸であるため，どちらの対角線も加えることができ，得ら れた三角形分割の 3色での彩色が警備員の適切な配置を与える．) ここでは簡単のため，
外領域も四角形とする．
ここで，各四角形面で “辺から入り反対側の辺へ抜ける”という操作を元の辺に戻るま で繰り返す．この操作で得られる辺の列 (双対の歩道) をリングとよぶことにする．どの 四角形も，あるリングにより 2回通過されている．ただし，そのリングは同じものかもし れないし, 異なるものかもしれない．各リングに適当に向きを付ける．その向きにした がって，各四角形面の対角線を次のように加え，三角形分割 T を得る；
対角線が，その四角形面を通るリングの向きにおいて，二つの終点と二つの 始点へと分割する．(図 29 を参照．)
この三角形分割 T で，各頂点の次数が偶数となることを示せばよい．
図 29: 四角形面におけるリング (点線) の向きと加えるべき対角線 (二重線)．
各頂点 v のまわりのリングの一部たちで構成される閉路Cv を考える．なお，Cv 上に は，「リングの交点」と「リングとQ の辺の交点」が交互に現れる．前者の集合をRv，後 者の集合をXv とおく．(図30参照．)特に |Rv|+|Xv|は偶数である．各 x∈Rv は次の 2通りに分類される．すなわち，リングの向きを Cv 上で見たときに，x で向きが変わる 場合と変わらない場合である．前者の数を r1,後者の数をr2 とおく．特に，r1+r2 =|Rv| である．また，Cv の向きはXv では変化しないことと向きの変化は必ず偶数回起こるこ とから，r1 は偶数となる．ここで，r2 に対応する箇所に対角線を入れることから，三角 形分割 T での頂点 v の次数は次のように計算でき，証明が完了する．
degT(v) = |Xv|+r2 = |Xv|+(
|Rv| −r1)
≡0 (mod 2). □
演習 ∗ 図31の四角形分割 (各面が四角形である平面グラフ)に適当に対角線を入れ，す べての頂点で次数が偶数である三角形分割を作れ．
v v
：リングの交点= Rv の点
：リングと Q の辺の交点 = Xv の点 図 30: 頂点v の周囲の状況の例 (左図) と，閉路 Cv，Rv および Xv (右図)．
図 31: