１．５個の頂点と４本の辺からなる連結なグラフをすべて書け。
［解答］ そのようなグラフは３つある。頂点の名前を A, B, C, D, E とする。
グラフ１の辺集合：{{A,B}, {B,C}, {C,D}, {D,E}}
グラフ２の辺集合：{{A,B}, {A,C}, {A,D}, {A,E}}
グラフ３の辺集合：{{A,B}, {A,C}, {A,D}, {D,E}}
［解説］ この問題では，同形なグラフを解答しても一つ分しか配点しない。
２．どのようなグラフにおいても，奇頂点は必ず偶数個であることを証明せよ。
［解答］ すべての奇頂点の次数の総和を x，すべての偶頂点の次数の総和を y とする。すべての頂点の次数の総和は辺の本数の２倍であるから，x＋y は偶数である。y は明らかに偶数なので，x も偶数でなければならない。x は奇数の和であるので，それが偶数になるには偶数個の奇数が必要である。従って，奇頂点は偶数個ある。
［解説］
辺の本数に関する数学的帰納法を用いて証明することもできる。任意の辺の両端点が，両方とも奇頂点の場合，両方とも偶頂点の場合，および，奇頂点と偶頂点の場合の３つの分けて説明すればよい。
具体的な例を挙げていくら説明しても，一般的な証明にはならない。
また，背理法を用いる場合，“奇頂点は必ず偶数個である”の否定を“奇頂点は必ず奇数個である”としてしまうと，奇頂点が偶数個ある例を一つあげて，矛盾が導かれる。しかしながら，“奇頂点は必ず偶数個である”の否定は“奇頂点が奇数個の場合がある”となる。
３．［問題のグラフはピーターセングラフと名付けられているもの。このグラフについては第７回の講義に載せてある。］
［解答］
(1) このグラフの直径は２
(2) このグラフの染色数は３
(3) このグラフは平面的グラフではないことの証明
このグラフは K3,3 と同相な部分グラフを含む。（どのようにすればよいかは，第７回の講義にある。）従って，クラトフスキーの定理からこのグラフは非平面的である。
［別解］
このグラフが平面的であると仮定すると，オイラーの公式から領域数は 7 となる。また，このグラフには長さが 4 以下の閉路は存在しないので，領域の次数は 5 以上である。従って，辺の本数 15 と領域の次数の関係から 2×15 = Σdeg(ri) ≧ 5×7 となり，これは矛盾である。
［解説］
このグラフは K5 に形が似ているので，K5 に同相であると答えている人が何人かいた。同相の定義をもう一度思い出してほしい。また，実際に K3,3 と同相な部分グラフを含むことを確認しておいて欲しい。
４．
(1) C(7,0) = 7!／(7!×0!) = 1［半分近くの人が 0 と答えていた。］
(2) P(10,3) = 10×9×8 = 720［何人かは C(10,3) を計算していた。］
(3) C(4,1)＋2C(4,2)＋3C(4,3)＋4C(4,4) = 32
(4) C(7,3)×C(4,2)×C(2,2) = 210
５．（重複順列の典型的な問題！）
(1) HTTP 4!／(2!) = 12
(2) QUEUE 5!／(2!×2!) = 30
６．
(1) C(8,5) = 56
(2) C(4,3)×(6,4) = 60
(3) C(4,2)×C(6,5)＋C(4,3)×C(6,4)＋C(4,4)×C(6,3) = 116
［(3) の別解］C(10,7)−C(4,1)×C(6,6) = 116
７．経過は８通り。樹形図らしきものを下に書く。
３→６→９→ [12]
└→７→ [10]
└→ [5]
└→４→７→ [10]
└→ [5]
└→２→ [5]
└→ [0]
└→ [1]