１．グラフ G(V, E) について。次の問に答えよ。ただし，V = {A, B, C, D, E, F}, E = {{A,B}, {A,D}, {B,E}, {B,F}, {C,F}, {D,E}} である。（このグラフを図に描いてから考えてください。）
(1) 頂点 A と C の距離 d(A, C) はいくらか。
【解答】
d(A, C) は，頂点 A から C への最短の道の長さである。そのような最短道は，頂点の列 (A, B, F, C) で表され，この道には３つの辺が含まれているので，d(A, C) = 3 である。
(2) このグラフの直径を求めよ。
【解答】
直径は，このグラフ上の任意の２頂点間の距離の最大値である。最も距離が大きくなる２頂点の片方は頂点 C となることは分かる。頂点 C から他の頂点への距離を調べると，d(C, D) = 4 が最大となる。よって，このグラフの直径は 4 である。
(3) このグラフに切断点はあるか。もしあればすべての切断点を列挙せよ。なければ『なし』と答えよ。
【解答】
切断点は B と F の２つ。C は切断点ではないことに注意せよ。
(4) このグラフはオイラーグラフか？ また，ハミルトングラフか？
【解答】
次数が奇数である頂点（奇頂点という）が B と C の２個あるので，オイラーグラフではない。（周回可能小道はあるが，閉じていないのでオイラー小道ではない。）
また，頂点 C は次数が１であるので C を通るような閉路（閉じた道なので，その通り道の次数は２以上でないといけない）は存在しない。従って，ハミルトン閉路は存在しない。つまりハミルトングラフでもない。
［頂点 C を通る閉路がないのだから，もちろんオイラー小道がないということもできる。］
(5) このグラフは２部グラフか？
【解答】
２部グラフである。頂点 A，E および F を左側に書き，残りの頂点を右側に書けば，すべての辺は左側の頂点と右側の頂点を結ぶことになる。
(6) このグラフから何本かの辺を除去して木にするには，何本を除去すればよいか。
【解答】
１本を除去すれば木になる。ただし，辺 {A,B}，{B,C}，{C,D} または {D,A} のいずれかを除去すると木になるが，これ以外の辺を除去しても木にはならない。つまり，このグラフに閉路がなくなるように辺を除去しなくてはならない。
２．グラフ G が与えられているとする。G の補グラフ G' は，G と同じ頂点集合をもち，G において２頂点 u と v の間に辺が存在しないとき，かつそのときに限り，G' において u と v の間に辺が存在するようにしてできるグラフである。次の問に答えよ。
(1) グラフ G(V, E) の補グラフ G' を書け。ただし，V = {A, B, C, D, E}, E = {{A,C}, {B,D}, {B,E}, {C,D}, {D,E}} である。（このグラフを図に描いてから考えてください。）
【解答】
補グラフ G' の辺集合 E' は E' = {{A,B}, {A,D}, {A,E}, {B,C}, {C,E}} となる。
(2) 上のグラフ G の隣接行列 A およびその補グラフ G' の隣接行列 A' を完成せよ。
【解答】... 行列は，いつものように書く。
A = [ 0 0 1 0 0 | 0 0 0 1 1 | 1 0 0 1 0 | 0 1 1 0 1 | 0 1 0 1 0 ]
A' = [ 0 1 0 1 1 | 1 0 1 0 0 | 0 1 0 0 1 | 1 0 0 0 0 | 1 0 1 0 0 ]
(3) 頂点数４のグラフ G で，G と G' が同形であるようなグラフを書け。
【解答】
長さ３の道。（図 5-26 の (d) のグラフ）
『練習問題：頂点数５のグラフ G で，G と G' が同形であるようなグラフは２種類ある。考えてみよ。また，頂点数６や７の場合はどうかも考えよ。』
(4) 頂点数８のグラフ G で，G と G' が同形であるとすれば，このグラフ G には辺が何本あるか。
【解答】
辺が n 本あるとすると，G' にも n 本ある。これらの和 2n は頂点数８の完全グラフの辺の本数 8×(8−1)／2 = 28 に等しい。すなわち，2n = 28 であるから，n = 14 である。