有限幾何学第12回提出課題6 問1（木に関する問題）ある国には都市が100あり，都市のいくつかは航空路で結ばれている．どの都市からも別の都市へ行けることは分かっている（中間の空港を経由する場合もある）．どこの都市からスタートしても全ての都市を197フライト以下で訪れることができることを示せ．ヒント：全域木提出課題6 問2（平面的グラフに関する問題）位数11の完全グラフのそれぞれの辺が赤または青に塗られている．このグラフから赤の辺だけからなるグラフ，青の辺だけからなるグラフを取り出す．この二つのグラフのうち少なくとも1つは平面的グラフではないことを示せ．ヒント：オイラーの公式の系1(1) 提出課題6 問3（有向グラフに関する問題）ある国の全ての町はほかの全ての町と一方通行の道路で結ばれてる．このとき，全ての町へ行けるような町が少なくとも1つあることを示せ．ヒント：トーナメントに向き付けされた根付き木（根から葉に向かって向き付けされている）が存在することを帰納法で示す．提出課題6 問4（彩色に関する問題）橋がない連結グラフ（地図と呼ぶ）が隣接している２つの面が同じ色にならないようにk色で面を彩色できるとき，地図はk-面彩色可能であるという．地図Gが2-面彩色可能であるための必要十分条件が Gがオイラーグラフであることを証明せよ．ヒント１：Gが２部グラフ⇔奇閉路を持たないヒント２：Gがオイラーグラフ⇔Gは辺素な閉路に分割できるヒント３：課題１１の問題２の手法を参照提出課題6 問5（問３を改良した問題）どんなトーナメントも長さが高々２の有向道によって他の任意の点に到達可能な１点を含む．ヒント：帰納法．頂点とその近傍（N+(v)）を取り除いて考える．提出課題6 今日の提出課題：問１，問２，問３レポート：内容：今回の提出課題の問４と問５提出日時：7月２４日の授業開始時注意：問４は解答が書いてあるwebサイトがいくつかありますが多くががかなり曖昧な解答．そのまま写さないようにしましょう．