１．グラフ G の頂点の最大次数を DG と表す。『任意のグラフ G は (DG＋1)−彩色可能である』ことを頂点数に関する数学的帰納法を用いて以下の手順で証明せよ。
(1) 頂点数が１および２のグラフは，(DG＋1)−彩色可能であることを示せ。
【解答】
頂点数１のグラフは K1 だけであり，このグラフの最大次数は 0 で，1−彩色可能であるから，命題は成立する。
頂点数が２のグラフは２種類あり，そのうちの辺をもたないグラフは，最大次数が 0 で，1−彩色可能であるから，命題は成立する。また，もう一つのグラフは K2 であり，その最大次数は 1 で，2−彩色可能であるからやはり命題は成立する。
(2) 頂点数が k の任意のグラフは (DG＋1)−彩色可能であると仮定すれば，頂点数が k＋1 のグラフは DG＋1 色を使って彩色できることを示せ。
【解答】
頂点数が k＋1 のグラフを G とする。G から任意の頂点 u および u に接続する辺を除いたグラフを H とする。
H の頂点数は k なので，H は (DH＋1)−彩色可能である。また，DH は DG より大きくなることはないので，H は (DG＋1)−彩色可能でもある。
G の u 以外の頂点に，H を DG＋1 色で彩色したように色をつける。u に接続する辺は DG 本以下であるので，u に隣接する頂点には使用されていない色が少なくともひとつは残っている。その色で u を彩色すれば，G を DG＋1 色で彩色できたことになる。
２．代数式 {(2 − xy)3}/{a2(b − c)} に対応する順序根付き木を書き，この式を前置式ポーランド記法で書き直せ。ただし，べき乗，乗法，除法として記号“↑”，“＊”，“／”を用いよ。
【解答】
順序根付き木は省略。
前置式ポーランド記法：／↑−２＊ｘｙ３＊↑ａ２−ｂｃ
３．２つのグラフ G1 と G2 について，次の問に答えよ。
ただし，G1 の頂点集合は V = {A, B, C, D, E, F} で，辺集合は E = {{A, B}, {A, C}, {A, D}, {A, E}, {B, D}, {B, F}, {C, E}, {C, F}, {D, F}, {E, F}} である。また，G2 の頂点集合は V = {A, B, C, D, E, F, G, H} で，辺集合は E = {{A, B}, {A, C}, {A, G}, {A, H}, {B, C}, {B, D}, {B, H}, {C, D}, {C, E}, {D, E}, {D, F}, {E, F}, {E, G}, {F, G}, {F, H}, {G, H}} である。
(1) グラフ G1 と G2 はともに平面的グラフである。それぞれを地図（辺が交差することなく描かれたグラフ）として書き直せ。各頂点には必ず名前をつけること。
【解答】省略
(2) グラフ G1 と G2 の染色数と，染色数個の色を使った彩色を答えよ。
【解答】彩色の方法は一例である。
G1 の染色数は３。
彩色の方法：色１＝{A, F}，色２＝{B, C}，色３＝{D, E}
G2 の染色数は４。
彩色の方法：色１＝{A, E}，色２＝{B, F}，色３＝{C, G}，色４＝{D, H}