■スモールワールド(その5)

 K6のすべての2頂点間を2色の線で結ぶと,点をつなぐ線がすべて赤かすべて青の三角形ができる.

(証)K6の頂点からは5本の線が発せられている.N(1)=2であり,

  5>2+2

であるから最低でも2色のうちどれかひとつの色は3回出現している.それが赤だと仮定する.この線分の先端にある3点のうち2点が赤で結ばれていたとすれば赤い三角形を形成する.どの2点も赤で結ばれていないとすると青い三角形を形成する.

===================================

[Q]n角形の美術館を警備するのに最低何人の警備員が必要だろうか?

[A] [n/3]人.

 「美術館定理」にもこれと同様の証明が用いられている.フバータルの問題に対するフィスクの解答は単純で美しいものであった(1978年).

[1]領域を三角形分割する.

[2]三角形の頂点を3色で塗り分けて,それぞれの三角駅の頂点に3色すべてが使われるようにする.

[3]使われた数が最も少ない色を指定し,そこに警備員を配置する.

===================================