１．５個の頂点と４本の辺からなる非連結なグラフをすべて書け。
［解答］そのようなグラフは３つある。頂点の名前を A, B, C, D, Eとする。
グラフ１の辺集合：{{A, B}, {B, C}, {C, A}, {D, E}}
グラフ２の辺集合：{{A, B}, {B, C}, {C, D}, {D, A}}
グラフ３の辺集合：{{A, B}, {B, C}, {C, A}, {A, D}}
［解説］この問題では，同形なグラフを解答しても一つ分しか配点しない。
２．有限で頂点数が２個以上ある木には，次数が１の頂点が少なくとも１個は存在することを示せ。
［解答］ 木であるから，頂点数を n とすると辺は n−1 本ある。頂点を P1，P2，...，Pn とし，すべての頂点の次数が２以上であると仮定すると，頂点の次数と辺の本数との関係から次式が成立する。
2(n−1) = deg(P1)＋deg(P2)＋...＋deg(Pn) ≧ 2＋2＋...＋2 = 2n
この式は明らかに矛盾である。よって，次数が１または０の頂点が少なくとも１個は存在するが，木は連結なので次数が０の頂点は存在しない。従って，頂点次数が１の頂点が少なくとも１個は存在することになる。
［解説］証明方法としてよく使われる手法の一つである背理法（結論を否定して矛盾を導く方法）を用いている。なお，グラフの辺の本数の２倍が，すべての頂点の次数の総和に等しいという定理（テキスト p.94，定理 5.1）は重要！
３．［問題のグラフは省略］
(1) 頂点 x と y の距離は４
(2) この地図の領域数は 11（10と答えた人は，外側領域を数え忘れた？）
(3) このグラフの染色数は２（つまりこのグラフは２部グラフ。２部グラフであることが次の問題へのヒントになっている。）
(4) このグラフにはハミルトン閉路が存在しない理由：
［(4) の解答］
このグラフの染色数は２なので，２色を使って実際に彩色してみると，片方の色の頂点は６個あり，もう一方の色の頂点は９個になる。２色で彩色されたグラフにおいては，どのような道であってもその道順には異なる色の頂点が交互に現れる。ところが，それぞれの色が付いた頂点の個数が異なるため，すべての頂点をちょうど一度ずつ通る閉路，つまりハミルトン閉路，は存在しえない。
［別解］
グラフ中央部に次数が２の頂点が３つある。ハミルトン閉路が存在すれば，それらの頂点を通るためにそれぞれに接続している２つの辺を必ず通るはずである。ところが，ハミルトン閉路が必ず通る６つの辺だけで閉路を構成してしまっているので，この閉路はこれら６つの頂点以外を通ることができない。従って，ハミルトン閉路は存在しない。
［解説］ ハミルトン閉路が存在しないことの証明は一般に難しい。それぞれのグラフの特徴を調べて，個々に考えるしかない。その中で，上記の［解答］に示した説明は理解しやすい。そのため，『ハミルトン閉路が存在しない理由』としては，よく利用される。
４．グラフの最大次数を DG とし，グラフの染色数を χ(G)とする。また，５個の頂点集合を {A, B, C, D, E} とする。
［解答］ 次の解答は一例である。
・DG−1 = χ(G) の例：辺集合＝{{A,B}, {A,C}, {A,D}, {D,E}}，DG = 3，χ(G) = 2
・DG = χ(G) の例：辺集合＝{{A,B}, {B,C}, {C,D}, {D,E}}，DG = χ(G) = 2
・DG＋1 = χ(G) の例：辺集合＝{{A,B}, {B,C}, {C,D}, {D,E}, {E,A}}，DG = 2，χ(G) = 3
［解説］ 問題には，条件として“連結グラフ”となっていることに注意。非連結グラフでも良い場合は，辺が０本で５つの頂点だけのグラフは DG＋1 = χ(G) である。
５．前置式ポーランド記法：−＊３ａ／＊ｂｃ＋↑ｄ２ｅ
６．最小全域木の辺の長さの総和は 18
［解説］最小全域木は何種類かある。解答用紙に『辺の長さも記入すること』と注意書きしておいたが，記入されていない解答が多かった。以後，注意すること。