2015年度有限幾何学中間試験解答問1 配布資料参照問2 (1) , (2) , (3), (5) 配布資料参照 (4) 赤のタイルを頂点とし，隣接する赤のタイル同士を辺で結んだグラフをGとする．このとき，問題の仮定より，Gの全ての頂点の次数は奇数となる．握手補題より，すべての頂点の次数の和は偶数であるので， Gの全ての頂点の次数が奇数であることから Gの頂点数が偶数であることが分かる．よって赤のタイルの個数は偶数である． (6) 位数nのグラフGに対して， Gの任意の非隣接な2頂点uとvに対して，dG(u)+dG(v)≧n-1が成立すると仮定する． V(G)以外の1頂点wとGの全ての頂点を辺で結んだグラフをG’とする．このとき，G’の任意の非隣接な2頂点uとvに対して，dG’(u)+dG’(v)≧(n-1)+1+1=|G’|が成立する．よってOreの定理より，G’はハミルトンサイクルCを持つ．このとき，C-wはGにおけるハミルトン道となる． (7) 略解例1：部集合A,Bの位数が|A|=(n-1)/2, |B|=(n+1)/2の完全2部グラフを考える（配布資料参照）．例2：完全グラフA,B (|A|=s, |B|=t, s+t=n-1)に対して， V(A)∪V(B)以外の1頂点とA，B全ての頂点を辺で結んだグラフを考える．このとき，非隣接な2頂点の最少次数和は，s+t=n-1となるが， vを取り除くと二つの成分に分かれることより，ハミルトングラフではない．問3 45 3 2 1 3 1 4 1 2 3 3 2 3 2 1 2 2 4