期末試験

執り行ないました．6問出題．割と標準的な問題ばかり出したと思ってます．解答時間は2時間半です．

1. 内周がkの平面的グラフの辺数の上界k(n-2)/(k-2)：Eulerの公式と二重の数え上げを組み合わせる．
2. 最小次数がkのグラフに長さ2kのパスが存在することの証明：誘導付きの問題．長いサイクルを求めるところはDiracの定理の証明と同じようにextremalityと鳩の巣原理を用いる．
3. 染色数がkのグラフの辺数がk choose 2以上であることの証明：いろんな方法で証明できるけど，袋小路に入ると抜け出せにくい問題．
4. 小問の集まりで，4問中2問選択
   1. Gのε正則分割がGの補グラフのε正則分割でもあることの証明：正則分割の定義が分かれば，素直にできる．
   2. 与えられた二部グラフの最大マッチングを見つける：証明には頂点被覆との弱双対性を用いる典型的な問題．
   3. 3正則ハミルトングラフが3辺彩色可能であることの証明：3正則グラフの頂点数が偶数であることを観察すれば素直にできる．
   4. ラムゼー数R(3,4)に対する上界R(3,4)≦9：ヒント通りまずR(3,4)≦10を示して，その証明からR(3,4)≦9を見出す．
5. 最大次数kのグラフにおける極大独立集合の大きさの下界n/(k+1)：これもいろんな方法で証明できる．極大性を使わないといけないことに注意．
6. 頂点数が偶数のr頂点連結グラフで，K_{1,r+1}を誘導部分グラフとして含まないものが完全マッチングを持つことの証明：ヒント通りTutteの定理を利用．取り除く頂点数がr以上のときは，取り除く頂点集合と残される奇成分の集合の間で辺の有無を二重に数え上げる．

受験者が少なかったので，すぐに採点しました．よくできた人と全然できなかった人の差がよく出ました．
受験した方はお疲れ様でした．