１． 次数列が ( 7, 6, 5, 4, 4, 4, 1, 1 ) である単純グラフは存在しないことを示せ。
＜Sol＞ どの頂点も次数が 7 の頂点と辺で結ばれている。また、次数が 6 の頂点と結ばれてない頂点は１個だけである。よって、次数が 1 の頂点は高々１個しかありえないので題意のようなグラフは存在しない。
２． 頂点数が２以上のどんな単純グラフも次数の等しい異なる２頂点を持つことを示せ。
＜Sol＞ ２点以上からなる連結成分が存在しないときはあきらかなので連結グラフについて示せば良い。
G を頂点数が２以上の連結単純グラフ、v を最大次数の頂点で deg(v) = p とする。
もし次数の等しい異なる２頂点がないとすると v に隣接する p 個の頂点の次数は 1 から p - 1 までの p - 1 個で（鳩ノ巣の原理により）それらのうちに次数の等しいのがあることになり不合理。
＜別解＞ 頂点数 n とすると各点の次数の可能性は 0 から n - 1 までである。
次数の等しい異なる２頂点が存在しないとすると次数 0 の点と次数 n - 1 の点がなければならないことになる。
次数 n - 1 の点は残りの n - 1 点のすべてと隣接しているのでこれは不可能。
３． n 頂点よりなる単純グラフ G のどの頂点の次数も (n - 1) / 2 以上であれば G は連結であることを示せ。
＜Sol＞ u, v を G の２点とする。 これらが結ばれてないとすると {u, v} と V(G) - {u, v} が n - 1 本以上の辺で結ばれているということになる。
|V(G) - {u, v}| = n - 2 なので（鳩ノ巣原理により）V(G) - {u, v} のどれかの点がこれらの辺のうちの２本と接合していることになる。
このことと G が単純なことからその頂点は u と v の両方に隣接していることになる。
４． n 頂点よりなる単純グラフ G が (n - 1)(n - 2) / 2 + 1 本以上の辺をもっているなら連結であることを示せ。
＜Sol＞ ２点以上をもつ成分が２つあったとして、それらの頂点数を p, q （p ≧ q）とすると、合計で高々 p(p - 1) / 2 + q(q - 1) / 2 本の辺をもつ。
それらをそれぞれ Kp+1, Kq-1 で置き換えると単純な計算で p - q + 1 本以上辺数が増加することがわかる。
よって、ひとつの成分が Kn - ξ + 1, 他の ξ - 1 個の成分はいずれも K1 のとき最大の辺数をもつことになる。
ξ ≧ 2 だと高々 (n - 1)(n - 2) / 2 本の辺しかもち得ないから ξ = 1 すなわち連結である。
５． 図の２つのグラフは同型であることを示せ。（Petersen グラフ）
＜Sol＞ X, Y を V のひとつの分割とすると X と Y を結ぶ辺の全体により２部全域部分グラフ H = H(X, Y) が定まる。
ε(H)＜ε(G)/2 であればある点 v があって v は自身が属さないクラスよりも自身が属するクラスと多くの辺で結ばれていることになる。
よって v の移動により分割を改変して行けば所望の２部全域部分グラフを得る。
７． f : V(G) → N ∪ {0} はすべての v ∈ V(G) に対して f(v) ≦ deg(v) であるとする。
G の全域部分グラフ Γ はすべての v ∈ V(G) に対して degΓ(v) = f(v) のとき G の f 因子（f-factor）とよばれる。
グラフ G に対してグラフ H で G が f 因子をもつことと H が 1 因子をもつことが同値であるようなのを構成せよ。
＜Sol＞ e(v) = deg(v) - f(v) とする。（ e は excess の頭文字 ）
まず G の各頂点 v を部集合 A(v) と B(v) のサイズがそれぞれ deg(v) と e(v) であるような完全２部グラフ Kdeg(v), e(v) に置き換える。
辺 v w に対して A(v) の頂点と A(w)の頂点を辺で結ぶ。但し、それらは隣接しないようにする。
８． n 立方体 Qn は２部グラフであることを示せ。
＜Sol＞ 1 が偶数個ある頂点全体と 1 が奇数個ある頂点全体が部集合となるから。
９． 平面グラフの非有界な面が丁度ひとつであることを示せ。
＜Sol＞ 各辺が有界なのでそれらが頂点で張り合わさってる平面グラフも有界で十分大きな半径の円に含まれる。
その円の外部はひとつの面に含まれるがそれが唯一の非有界な面となっている。
１０． 頂点を３次元ユークリッド空間の点 (1, 12, 13), (2, 22, 23), (3, 32, 33), . . . にすればどんな単純グラフも各辺が線分であるように空間に実現できることを示せ。
＜Sol＞ 異なる４点 P(p, p2, p3), Q(q, q2, q3), R(r, r2, r3), S(s, s2, s3) を頂点とする４面体（つぶれているかも知れないが）の体積は良く知られてるように行列式で表されそれは 0 には成りえないことがわかる。
１１． 双対な概念の例を考えよ。
＜Sol＞ 頂点の除去の双対は「面の縮約」になる。
１０章で「生成木」の双対が「補木」であることが示される。
１２. X ⊂ V(G) の X に対して X に属する頂点と V(G) - X に属する頂点を結ぶ辺の個数を f(X) とする。
任意の X, Y ⊂ V(G) について f(X) + f(Y) ≧ f(X∩Y) + f(X∪Y) が成り立つことを示せ。
＜Sol＞ S1 = X - X∩Y, S2 = X∩Y, S3 = Y - X∩Y, S4 = V(G) - X∪Y とおく。
また A, B ⊂ V(G) に対して A の点と B の点を結ぶ辺の総数を (A, B) で表示する。
すると
f(X) = (S1, S3) + (S1, S4) + (S2, S3) + (S2, S4)
f(Y) = (S2, S1) + (S2, S4) + (S3, S1) + (S3, S4)
f(X∩Y) = (S2, S1) + (S2, S3) + (S2, S4)
f(X∪Y) = (S1, S4) + (S2, S4) + (S3, S4)
∴ (f(X) + f(Y)) - (f(X∩Y) + f(X∪Y)) = 2(S1, S3) ≧ 0.
【 NOTE 】 単調増加性（ i.e. X ⊂ Y ⇒ f(X)≦f(Y) ）も満たすようにするには X に属する頂点どうしか X に属する頂点と V(G) - X に属する頂点を結ぶ辺（つまり X に接合する辺）の個数を f(X) とすれば良い。
１３． どんなグラフ G に対してもそれを部分グラフとする Δ(G) 正則なグラフが存在することを示せ。 またどんな２部グラフ G に対してもそれを部分グラフとする Δ(G) 正則な２部グラフが存在することを示せ。
第２章
１． 対称差 Δ に関する次の公式を証明せよ。
（１） (A Δ B) Δ C = A Δ (B Δ C)
（２） (A Δ B Δ C) ∪ X = (A ∪ X) Δ (B ∪ X) Δ (C ∪ X) （ Nagata の公式 ）
（３） (A ∇ B) ∇ C = A ∇ (B ∇ C) = A Δ B Δ C． 但し A ∇ B = (A Δ B)c．
＜Sol＞ （１） 全体集合 U とし、その部分集合 A に対して
（標数 2 の）特性関数 χA： U → {0,1} （= Z/2Z） を、
0 x ∈ U - A
χA(x) = ｛
1 x ∈ A
として定義する。 A = B ⇔ χA = χB である。
χ(AΔB)ΔC = χAΔB + χC
= (χA + χB) + χC
= χA + (χB + χC)
= χA + χBΔC
= χAΔ(BΔC)
∴ (AΔB)ΔC = AΔ(BΔC)．
（２） （ by coolee ） 一般のブール環 R で示す。（ すべての元がべき等である環をブール環 ）
ch R = 2 である。（ ∵ x + x = (x + x)2 = x2 + x2 + x2 + x2 = x + x + x + x ∴ x + x = 0 ）
x ∪ y := x + y + xy と定義すると
x ∪ (y1 + y2 + y3) = x + (y1 + y2 + y3) + x(y1 + y2 + y3)
= x + x + x + y1 + y2 + y3 + xy1 + xy2 + xy3
= (x ∪ y1) + (x ∪ y2) + (x ∪ y3)
ベキ集合 P(A ∪ B ∪ C ∪ X) において加法を Δ、乗法を ∩ とするとブール環で、 J ∪ K = J Δ K Δ (J ∩ K) となっている。
（３） A ∇ B = Ac Δ B = A Δ Bc となっている。
∴ (A ∇ B) ∇ C = ((A Δ B)c Δ C)c
= (A Δ B)cc Δ C
= A Δ B Δ C
= A Δ (B Δ C)cc
= (A Δ (B Δ C)c)c
= A ∇ (B ∇ C)．
２． 連結グラフ G の生成木 T について |T| = |V(G)| - 1 であることを示せ。
＜Sol＞ 木の端点を除去しても木であり（なぜ？）端点の除去を繰り返すと最終的に K1 になる。このことから |T| = |V(T)| - 1.
ここで V(T) = V(G) ゆえ所望の式を得る。
【 NOTE 】 木の端点を除去しても木であることは連結性と非輪状性が保たれることより言える。
３． グラフ G の辺の集合 T （の誘導部分グラフ）の頂点が n 個であるとき、次が同値であることを示せ。
（T1） T は木である.
（T2） T はサーキットを含まず |T| = n - 1.
（T3） T は連結で |T| = n - 1.
（T4） T は連結でどの要素も ＜T＞ のブリッジである.
（T5） ＜T＞ の異なる２点に対してそれらを結ぶバインダーが一意的に存在する.
（T6） ＜T＞ の異なる２点に対してそれらを結ぶパスが一意的に存在する.
（T7） T はサーキットを含まないが ＜T＞ に辺を付加すると丁度１個のサーキットを含むようになる.
＜Sol＞ n = 1 ならあきらかゆえ、n ≧ 2 と仮定する。
（T1）⇒（T2）⇒（T3）⇒（T4）⇒（T5）⇒（T6）⇒（T7）⇒（T1）を示せばよい。
４. グラフ G の辺の集合 N について次が同値であることを示せ。
（N1） N はナーブである.
（N2） どのコサーキットとも交わり、サーキットを含まない.
（N3） どのコサーキットとも交わり、そのような辺の集合のうち極小.
（N4） どのコサーキットとも交わり、|N| = |V(G)| - ξ(G).
（N5） サーキットを含まず、|N| = |V(G)| - ξ(G).
＜Sol＞ （N1）⇒（N2）⇒（N3）⇒（N4）⇒（N5）⇒（N1）を示せばよい。
５. どんな木 T も少なくとも Δ(T) 個の端点を持つことを示せ。
＜Sol＞ v を最大次数の頂点, P1, P2, . . . , PΔ(T) を v の隣接点とする。
v を始点とし Pi を通る極大なパスの終点を wi とすると w1, w2, . . . , wΔ(T) は T の端点でいずれも異なる。
＜別解＞ d1, d2, . . . , dn を T の頂点の次数とする。
これらの中に 0 があれば T = K1 であきらかに成立する。
そこでこれらのいずれもが 1 以上とする。
T の端点の数 h とし h＜Δ(T) と仮定する。
d1 = d2 = . . . = dh = 1, dh+1 = Δ(T) とすると dh+2 から dn まではいずれも 2 以上で
Σi di = h + Δ(T) + dh+2 + . . . + dn
≧ h + Δ(T) + 2(n - (h + 1))
= 2n + (Δ(T) - h) - 2
≧ 2n - 1.
これは Σi di = 2(n -1) に反する。
６. T が k 個の辺をもつ木，G が δ(G) ≧ k の単純グラフであれば T は G の部分グラフとなることを示せ。
＜Sol＞ k = 0 であれば T = K1 で、V(G)≠φ であるから確かに成り立っている。
帰納的に k ＞ 0 とし k 個未満の辺をもつ木に関しては成り立っていると仮定する。
k ≧ 1 より T は２個以上の頂点をもつことになるので端点 v が存在し v の T における唯一の隣接点を u とする。
δ(G) ≧ k ＞ k - 1 ゆえ帰納法の仮定より G は T - v のコピー H を含む。
H において u に対応する頂点を x とする。
T - v は u 以外の頂点を k - 1 個だけもつので x は G における隣接点 y で V(H) に属さないのをもつ。
H に辺 xy を付加したものは T と同型である。
７. n ≧ 2 の正整数の非増加な列 ( d1, . . . , dn ) について、ある木の次数列となることと Σdi = 2(n - 1) が同値であることを証明せよ。
＜Sol＞ 必要性はあきらかなので十分性を n に関するインダクション（帰納法）で示す。
n = 2 のとき． Σdi = 2(2 - 1) = 2 となる列は (1, 1) のみで木 K2 の次数列となっている。
n ＞ 2 のとき． Σdi ＞ n なので d1 ≧ 2 である。また、di ＜ 2n なので dn ≦ 1，よって dn = 1 である。
列 (d1 - 1, d2, . . . , dn-1) は Σdi = 2((n - 1) - 1) で帰納法の仮定からある木の次数列である。
ひとつの新しい頂点を加えて次数が d1 - 1 の頂点と辺で結べば望む木をえる。
８. τ(K2,n) = n 2n-1 であることを示せ。
＜Sol＞ K2,n の部集合を {u1, u2}, {v1. v2, . . . , vn} とする。
K2,n の全域木は各 i について u1vi と u2vi のうち１本と更にあと１本の辺よりなる。
∴ τ(K2,n) = (2n×n)/2 = n 2n-1.
９. 連結グラフにおける２つの最長なパスは頂点を共有することを示せ。
＜Sol＞ 頂点を共有しない最長なパス π1 と π2 があったとして π1 は u1v1 パス、π2 は u2v2 パスとする。
π1 の点から π2 の点へのパス π の π1 を最後に離れる点を P, 次に π2 に到着する点を Q とする。
|π1(u1, P)|≧|π2(u2, Q)| と仮定して一般性を失わない。
このとき |π1(v1, P)|≦|π2(v2, Q)| であることになる。
すると |π1(u1, P)∪π(P, Q)∪π2(v2, Q)| は |π1|, |π2| よりも大となり不合理。
【 NOTE 】 π1 の点から π2 の点への最短なパスを使ってもよい。
１０. 単純グラフ G のかってな点 v に対して v を始点とする長さ d(v) のパスがとれることを示せ。
＜Sol＞ v を始点とする最長のパスのひとつを π とする。 v に隣接する頂点のうちに π に属さないのがあれば π より１だけ長いパスが構成できることになり不合理ゆえ v に隣接する頂点はいずれも π に属していなければならないことになる。
よって π には d(v) + 1 個以上の頂点があることになりこれは π の長さが d(v) 以上であることを意味している。
１１. δ(G) ≧ 2 の単純グラフは長さが少なくとも δ(G) + 1 のサーキットをもつことを示せ。
＜Sol＞ １０ の解において v から最も離れている π 上の v の隣接点を w とする。
π(v, w) ∪ {vw} は求めるサーキットである。
１２. 連結グラフにおいて距離 dist(u, v) は距離空間の公理を満たしていることを示せ。
＜Sol＞ dist(u, v) ≧ 0 である。
dist(v, v) = 0 と dist(u, v) = dist(v, u) はあきらか。
dist(u, v) + dist(v, w) ≧ dist(u, w)． dist(u, v) を与えるパスを π1，dist(v, w)を与えるパスを π2 とする。
u から π1 をたどって最初に π2 にぶつかる頂点を P， w から π2 をたどって最初に π1 にぶつかる頂点を Q とする。
π1(u, P) ∪ π1(P, Q) ∪ π2(Q, w) は u w パスでその長さは π1 の長さとπ2 の長さの和以下である。
１３. T1, T2, . . . , Tk が木 T の部分木でどの２つも頂点を共有するとき全体として共有する頂点が存在することを示せ。
＜Sol＞ T1, T2, . . . , Tk のいずれかが K1 であればその頂点は ∩V(Ti) に属する。
よって、T1, T2, . . . , Tk はいずれも２点以上からなるとする。
v を T のひとつの端点とする。
T1, T2, . . . , Tk を T - v に制限しても木であり、もしもそのうちの２つが頂点を共有していないとするとそれらは制限する前には v を共有していたことになるがこのときそれに隣接する頂点も必ず共有していることになり不合理。
よって T1, T2, . . . , Tk を T - v に制限した木もどの２つも頂点を共有する。
T1, T2, . . . , Tk を T - v に制限した木の中に K1 があればその頂点が ∩V(Ti) に属することになる。
以下これを繰り返すとどれかが K1 になるので成り立つことがわかる。
１４. 連結グラフの商グラフも連結であることを示せ。
＜Sol＞ G を連結グラフとする。ひとつの辺 e による縮約でえられる商グラフ G/e が連結なことを示せばよい。
G/e の任意の異なる２頂点 u, v に対して G には uv バインダー B が存在する。B - {e} は G/e での uv バインダーとなる。よって G/e も連結である。
第３章
１． 奇グラフのナーブ N の枝 x に対して次は同値であることを示せ。
（１） x ∈ z(N)
（２） N - x のどの連結成分も頂点数が even
＜Sol＞ G を奇グラフとする。x ∈ z(N) ⇔ |γ(x ; N)| ≡ 0 (mod 2) である。
N の成分は木でそのうち x を含むのを T とする。
グラフの奇点は偶数個であることから T 以外の N の成分の頂点数は even である。
T - x は２つの木の素和で、それらを T1, T2 とする。
γ(x ; N) は V(T1) に属する頂点の G におけるコバウンダリーの総和で、 G が奇グラフであることから G のどの頂点のコバウンダリーもサイズが odd なので |γ(x ; N)| ≡ 0 (mod 2) であることと |V(T1)| が even であることは同値であることになる。
同様に |V(T2)| が even であることとも同値ゆえ (1) と (2) は同値である。 //
２. 頂点を偶数個持つ連結な偶グラフの全域木の総数は even であることを示せ。
＜Sol＞ 全域木を頂点とし２つの全域木が１辺どうしの入れ替えで移れるとき辺で結んでえられるグラフ Γ とする。
そのような入れ替えは全域木の枝に付随する基本コサイクルの中でのみ制限なしに行えるので、 E(G) がサイクルなことからコサイクルの辺の数は偶数で全域木の枝はそれよりひとつ少ない奇数本と入れ替え可能なことになる。
また頂点数が偶数なので全域木の辺の数はそれよりひとつ少ない奇数である。
よって、奇数個の奇数の和は奇数であることから Γ のどの頂点も奇点である。
どんなグラフの奇点も偶数個あるから Γ の頂点数は even ということになりこれは題意を意味している。
３. 頂点数と辺数の偶奇が等しい連結２部グラフの全域木の総数は even であることを示せ。
＜Sol＞ ２と同じようにして示せる。
第７章
１． ２つの完全マッチング M, M' に対して、＜M ∪ M'＞ の成分は K2 か長さが偶数のサーキットであることを示せ。
＜Sol＞ ＜M ∪ M'＞ を H とおく。
H の各頂点の次数は 1 か 2 である。
次数 1 の頂点 v に隣接する一意的な頂点を w とすると M も M' も辺 v w を含むことになり v も w も M ∪ M' に接合しえないから辺 v w を含む連結成分は K2 となる。
次数 1 の頂点を含まない連結成分はサーキットであり M と M' の辺が交互になければならないから長さが奇数ということはありえない。
２． ２人のプレーヤーが交互に連結グラフ G の異なる頂点 v1, v2, . . . を隣接しているように選んで行く。最後に頂点を選べたほうが勝ちとするとき、次は同値であることを示せ。
（１） 最初のプレーヤーが必ず勝てる．
（２） G は完全マッチングをもたない．
＜Sol＞ (1)⇒(2)． 対偶を考えるとあきらか。
(2)⇒(1)． M を最大マッチングとする。
最初のプレーヤーはまず M に接合してない頂点を選ぶ。
次のプレーヤーが M に接合してない頂点を選べたとすると M が最大であることに反する。
最初のプレーヤーは M でマッチされている頂点を選んで行く。
ある時点で次のプレーヤーが M に接合してない頂点を選べたとすると M 増大道が存在することになり矛盾するから、このような戦術により最初のプレーヤーは必ず勝てるということになる。
３． どんな最大次数が１以上の２部グラフもすべての最大次数の頂点と接合するマッチングをもつことを示せ。
＜Sol＞ G = G(X, Y) を２部グラフ，|X| ≧ |Y| とする。
Y に |X| - |Y| 個の頂点を追加してそれを Y' として、G を Δ(G) 正則な２部グラフ G' = G'(X, Y') に拡大できる。
G'(X, Y') は結婚定理により完全マッチングをもつ。それを G に制限すると所望のマッチングがえられる。
４． 図のグラフは完全マッチングをもたないことを示せ。
＜別解＞ 完全マッチングが存在したとしてそのうちのひとつ M とする。
よって、辺 u1v は M に属さねばならない。
同様にして、辺 u2v と 辺 u3v も M に属さなければならないことになるがこれは M が完全マッチングであることに反する。
５． 木は完全マッチングを高々ひとつしかもたないことを示せ。
＜Sol＞ 異なる２つの完全マッチングをもったとする。それらの対称差は空でないサイクルとなり不合理。
６． T を木、v をひとつの端点とすると、T は v に接合する最大マッチングをもつことを示せ。
＜Sol＞ v に隣接している頂点を w とする。また、M をひとつの最大マッチングで v に接合していないとする。
M が w に接合していなければ辺 v w を加えてより大きなマッチングを作れることになり不合理なので M は w に接合していることになる。
w に接合している M の辺を辺 v w と置き換えてもマッチングでサイズが M と同じなので最大である。
７． 木 G について次が成り立つことを示せ。
G は完全マッチングをもつ ⇔ ∀v ∈ V(G), o(G - v) = 1. （ Chungphaisan ）
＜Sol＞ ⇒． v をひとつの頂点 ，M をひとつの完全マッチングとする。
v に接合する M の辺 v w とすると、G - v の成分は w を含むのが奇成分で他はいずれも偶成分である。
逆． 頂点 v に対して G - v の唯一の奇成分の頂点で v に隣接してるのが一意的に存在する。
それを f(v) とすると、f(f(v)) = v となっているから { v f(v) | v ∈ V(G) } は完全マッチングである。
８． Tutte-Berge の公式を証明せよ。
＜Sol＞ 2 α'(G) = minS⊂V (ν(G) - (o(G - S) - |S|)) (*)
を示せばよい。
任意の S ⊂ V について、
2 α'(G) ≦ 2 (|S| + α'(G - S)) ≦ 2 (|S| + (1/2)(|ν - S| - o(G - S))) = ν - (o(G - S) - |S|)
∴ 2 α'(G) ≦ minS⊂V (ν(G) - (o(G - S) - |S|))
この上限が達成されることを示す。
d = minS⊂V (o(G - S) - |S|) とおく。S = φ のケースから d は非負である。
G' = G * Kd とする。各 S について o(G - S) - |S| は ν(G) とパリティーが一致するので ν(G') は偶数である。
もしも G' が Tutte の条件を満たしていれば G' の完全マッチングから望むサイズの G のマッチングをえることができる。
o(G' - S') ≦ |S'| は S' = φ のときは ν(G') が偶数であることから成り立っている。
S' が空でなくて V(Kd) を含んでいなければ G' - S' は成分が１個なので成立する。
S' が空でなくて V(Kd) を含んでいるとき、S = S' - V(Kd) とする。
G' - S' = G - S ゆえ o(G' - S') = o(G - S) ≦ |S| + d = |S'|．
＜別解＞（直接証明） (*) の ≧ の部分を ν(G) の帰納法で示す。 V = φ のときはあきらか。
G が非連結であれば各成分に帰納法を適用して示せるから G は連結と仮定できる。
どの最大マッチングにも接合する頂点 v があったとすると α'(G - v) = α'(G) - 1 で、また帰納法から V - {v} の部分集合 S' が存在して
α'(G - v) = (1/2){|V - {v}| + |S'| - o(G - v - S')}.
このとき S = S' ∪ {v} は (*) で等号を成り立たせることになる。
よってそのような v は存在しないと仮定できる。とくに、α'(G) ＜ |V| / 2 である。
サイズが (|V| - 1) / 2 のマッチングが存在することを示せば S = φ で (*) がえられる。
どの最大マッチングも２点 u, v と接合しないと仮定してそのような M, u, v のうちから距離 dist(u, v) が最小のを選ぶ。
dist(u, v) = 1 なら u と v は隣接しているから M に辺 u v も加えると |M| の最大性に反することになる。よって dist(u, v) ≧ 2 とし、最短 u v パス上の途中の点 t を選んでおく。
仮定から t と接合しない最大マッチング N が存在するが、そのような N の中で |M ∩ N| が最大のを選ぶ。
dist(u, v) の最小性から N は u と v の両方と接合していることになる。
M と N は接合している頂点の数がひとしいからある t でない頂点 x で M には接合してるが N には接合してないのが存在する。
e = x y ∈ M とする。
y が N のある辺 f に接合していないとすると N ∪ {e} は N より大きなマッチングということになるので y は N のある辺 f に接合していることになる。
(N - {f}) ∪ {e} は N よりも余計に M と交わっていて N の選び方に反することになる。
【 NOTE 】 Tutte-Berge の公式から Tutte の 1 因子定理が導かれる。
（∵） 完全マッチングをもつ ⇔ ν = minS⊂V (ν - (o(G - S) - |S|))
⇔ ν = ν - maxS⊂V (o(G - S) - |S|)
⇔ maxS⊂V (o(G - S) - |S|) = 0
⇔ ∀S⊂V, o(G - S) ≦ |S|
９． ２部グラフ G(X, Y) の最大マッチングのサイズは |X| - maxS⊂X ( |S| - |N(S)| ) であることを証明せよ。
＜Sol＞ M を最大マッチング，h = maxS⊂X ( |S| - |N(S)| ) とおく。
h 個の頂点を Y に付け加えてそれら h 個の頂点の各々を X のすべての頂点と結ぶと Hall の定理の条件が満たされるから X のすべての要素に接合するマッチングが存在する。
高々 h 個の X の頂点が付け加えた頂点に接合していることから少なくとも |X| - h 個の頂点は G の頂点とマッチされている。よって、|M| ≧ |X| - h ．
X' を M と接合する X の頂点全体の集合とする。
G' = ＜X' ∪ Y＞ とおくと、Hall の定理によりすべての S ⊂ X' に対して |NG'(S)| ≧ |S| である。
よって、すべての S ⊂ X に対して |NG(S)| ≧ |NG'(S ∩ X')| ≧ |S ∩ X'|．
したがって S を h を達成する X の部分集合とすると、
|X| - h = |X| - (|S| - |NG(S)|)
≧ |X| - ( |S ∩ X'| - |NG'(S ∩ X')| + |S - X'| )
≧ |X| - |S - X'|
≧ |X'| = |M|
１０． 定理 7.2（Hallの定理）を定理 7.3（König の定理）から導け。
１１． 最大マッチング M* と極大マッチング M に対して |M|≧ |M*| / 2 であることを示せ。
１２． 図の図形はドミノ（1×2 のタイル）では敷き詰めできないことを示せ。
第８章
１． Hall の定理を最大フロー・最小カットの定理を使って示せ。
＜Sol＞ 新しい点 s, t を使って s*XG*Yt の辺を s から t に向かって向き付けしてえられる有向グラフを D とし、弧の容量は s からの弧と t への弧を 1，その他は ∞ としてえられるネットワーク (D,s,t,c) を N とする。
cap({s} , {s}c) = |X| ＜ ∞ なので整数最大フローが存在する。
整数フロー f は X のすべての要素に接合するマッチング
M = { uv ∈ E(G) | f(uv) = 1 }
を定め逆も成り立つ。
(S , T) （ T = Sc ）をカット、S1 と S2 はそれぞれ S を X と Y に制限したものとする。 (S , T) が有限の容量であることと N(S1) ⊂ S2 とは同値である。
このとき cap(S , T) = (|X| - |S1|) + |S2| である。
また最大フロー・最小カットの定理の定理より
max M |M| = min S1⊂X, N(S1)⊂S2⊂Y (|X| - |S1|) + |S2|
= min S1⊂X (|X| - |S1|) + |N(S1)|
よって X のすべての要素に接合するマッチングが存在する ⇔ max |M| ≧ |X|
⇔ |X| - |S1| + |N(S1)| ≧ |X| （ ∀S1 ⊂ X ）
よって示された。
第９章
１． 連結グラフ G について次は同値であることを証明せよ。
（１） 分離集合をもつ．
（２） 非隣接な２点が存在する．
＜Sol＞ (1)⇒(2). 対偶を考えるとあきらか。
(2)⇒(1). u, v を非隣接とする。G が連結なので uv パスが存在するがその長さは２以上で u, v 以外の点を通る。そのうちのひとつ w とする。
G - w が非連結なら {v} は分離集合である。
G - w が連結なら同様な操作を繰り返せばよい。
２． 頂点数が２以上の連結グラフは切断点でない頂点を２個以上もつことを示せ。
＜Sol＞ G を条件を満たすグラフ、T をその全域木とする。
T は端点を２個以上持ちそれらは T の切断点ではないので T は切断点でない頂点を２個以上もつ。
v を T の非切断点とすると ξ(T - v) = 1.
T - v は G - v の全域部分グラフかつ ε(G - v)≧ε(T - v) より ξ(G - v)≦ξ(T - v).
∴ ξ(G - v) = 1. よって、v は G の非切断点である。
３． かってな整数 1≦r≦s≦t に対して κ = r, λ = s, δ = t である単純グラフが存在することを示せ。
＜Sol＞ Kt+1 のコピー A と B をとっておく。
A から r 個の点 v1, . . . , vr , B から s 個の点 w1, . . . , ws を選んで、bi (1≦i≦r) を ai と辺でつなぎ bj (r+1≦j≦s) をかってな aq と辺でつなぐ。
こうして得られるグラフは題意のグラフとなっている。
４． κ(Qn) = n を示せ。
＜Sol＞ n についての帰納法で示す。
n = 0, 1 のときはあきらか。
n ≧ 2 とし κ(Qn - 1) = n - 1 と仮定する。
Qn は n 正則で δ(Qn) = n なのでサイズが n の分離集合は存在するからどんな分離集合もサイズが n 以上であることを示せばよい。
S を Qn の分離集合とする。
Qn は Qn - 1 の２つのコピー A と B を対応する頂点どうしを 2n - 1 本の辺でマッチさせてえられるグラフとなっている。
A - (V(A) ∩ S) も B - (V(B) ∩ S) も連結とすると S がどのマッチされている頂点のペアのうちの少なくともひとつを含まなければ G - S が非連結とはならない。
すると |S| ≧ 2n - 1 ≧ n．（ ∵ n ≧ 2 ）
よって A - (V(A) ∩ S) は非連結としてかまわない。
帰納法の仮定で |V(A) ∩ S| ≧ n - 1 である。
|V(B) ∩ S| = 0 だと Qn - S は連結となってしまうので |V(B) ∩ S| ≧ 1 でなければならないから |S| ≧ n となる。
５． 単純な３正則グラフ G に対しては κ(G) = λ(G) であることを示せ。
＜Sol＞ 1 ≦ κ(G) ≦ λ(G) ≦ δ(G) ≦ 3 ゆえ κ(G) は 1 か 2 か 3 である。
Case 1: κ(G) = 3. あきらかに λ(G) も 3 である。
Case 2: κ(G) = 2, 下の図から λ(G) も 2 である。
いつでも κ(G) ≦ λ(G) は成り立っているので κ(G) = λ(G)．
６． κ(v * G) = κ(G) + 1 を示せ。
＜Sol＞ G が完全グラフおよび完全グラフに辺をいくつか付加したグラフであれば v * G もそうであるからあきらか。
G が完全グラフおよび完全グラフに辺をいくつか付加したグラフでないとき v * G もそうであり分離集合をもつが v を含まないと分離集合になりえないことからあきらか。
７． ２連結グラフ G のかってな頂点 v に対して v と隣接する頂点 u で G - u - v が連結となるのが存在することを示せ。
＜Sol＞ G が２連結なので G - v は連結である。
G - v が２連結なとき． u は v のどの隣接点でもＯＫ．
G - v が２連結でないとき． G - v のブロックでちょうどひとつの G - v の切断点をもつのが存在する（なぜ？）のでそのうちのひとつを B としその切断点を x とする。
v が B - x に隣接点をもたないとすると G - x は B - x を連結成分とする非連結グラフとなってしまうから v は B - x に隣接点をもつ。
それを u とすると B - u は連結なので G - u - v も連結となる。
８． 頂点数が５以上のどんな３連結グラフ G も、G/e がやはり３連結となるような辺 e をもつことを示せ。（ Thomassen ）
＜Sol＞ そのような辺が存在しないと仮定する。
するとどの辺 e = xy についても G/e は２点を除去することで非連結にできることになる。
縮約でできた頂点 vxy はこれら２点に含まれているはずであり、もうひとつの頂点を z とすると G/e において {vxy, z} により分離される２点は G において {x, y, z} により分離される。
分離集合の最小サイズが３となることから x, y, z のいずれも G - {x, y, z} の各成分のある頂点と隣接していることになる。
辺 e, 頂点 z, 成分 C を |V(C)| が最小になるように選んでおく。
また、z に隣接する C の頂点 v を選んでおく。
先と同様、ある頂点 w が存在して {z, v, w} は G を分離し z, v, w のいずれも G - {z, v, w} の各成分のある頂点と隣接していることになる。
x と y は隣接しているので G - {z, v, w} の成分 D で x も y も含まないのが存在する。
v が C に属することから v と隣接する D の頂点も C に属するので D ∩ C ≠ φ であり D の選び方から D は C の真部分集合であることになる。
これは |V(C)| が最小であったことに反する。
９． G の頂点の集合 S は κ(v *S G) = κ(G) + 1 をみたすとき （点連結度についての）持ち上げ集合（lifting set）とよぶことにする。
単純グラフ G については、n 連結かつ n 正則であることと持ち上げ集合は V(G) のみであることとは同値であることを示せ。
１０． 図の２つの連結グラフはどちらもハミルトングラフではないことを示せ。
右のグラフにおいて、頂点 a, c, g のそれぞれにおいて接合する３本の辺のうち１本はハミルトンサーキットに属せない。また、頂点 i に接合する４本のうち２本も属せない。
頂点数とハミルトンサーキットの長さは等しいのでハミルトンサーキットの長さは１１である。
ところが、a, c, g, i が非隣接なことから１５本の辺のうち前記の５本はハミルトンサーキットに属せない。これは不合理。
＜Sol＞ C をハミルトンサーキットとする。また、S は空ではないので S に属する頂点がありそのひとつを v とする。
v から C を一巡して v に戻るまでに G - S の成分から離れる回数 k とすると
|S| ≧ k ≧ ξ(G - S). ∴ |S| ≧ ξ(G - S)．
【 NOTE 】 S が空集合のとき題意の不等式が成立しないことに注意。また、題意の不等式から G は切断点をもたないことが必要であることがわかる。
１２． 頂点数が３以上で κ(G) ≧ α(G) のグラフはハミルトングラフであることを示せ。（ Chvatal-Erdös ）
＜Sol＞ ハミルトンサーキットをもたないと仮定する。
C を最長のサーキット、H を G - C の連結成分とする。
κ(G) を k とおくと条件から k ≧ 2 で、δ(G) ≧ κ(G) であるから δ(G) ≧ 2 となって２章の問題１０より C は k + 1 個以上の頂点をもつ。
C は H への k 個以上の頂点を持たなければならず、u1, u2, . . . , uk を C をまわる向きの順でのそのような頂点たちとする。
また、ai を C 上で ui の次に来る頂点とする。
ある２つの ai と aj が隣接しているとすると図のようにして C より長いサーキットができてしまうのでどの ai と aj も隣接していないことになる。
a1, . . . , ak と H のひとつの頂点とでサイズが k + 1 の独立集合がえられることになり不合理。
１３． 奇グラフのひとつの辺を通るハミルトンサーキットの総数は even であることを示せ。（ Smith-Thomason ）
＜Sol＞ ひとつの辺を e = uv とする。e がループなら 0 個で even なので e はリンクとする。
u からスタートして辺 e を通るハミルトンパスの全体を頂点集合とし、終点に新しい辺を付け加えて他の辺を除去して得られるときに隣接させたグラフを考えてみると、奇点は e を通るハミルトンパスと１対１に対応する。よって成り立つ。
【 NOTE 】 この定理は Smith が 3 正則グラフで示したのを Thomason が一般化したものである。
第１０章
１． 定理 10.1 の最初の系は非連結でも成り立つか。
＜Sol＞ 平面的グラフ G の頂点、辺、面、成分の数を v，e，f, ξ とする。
G に ξ - 1 本の辺を成分どうしを結ぶように付加して連結な平面的グラフ G~ にすることができる。
G~ の頂点数、辺数、面数は v, e + ξ - 1, f であるからオイラーの公式より
v - (e + ξ - 1) + f = 2．
よって f = ξ + 1 - v + e となり、平面的実現の面の数は埋め込みによらず一定といえる。
２． どんな単純平面グラフも次数が 5 以下の頂点を持つことを示せ。
＜Sol＞ G を単純平面グラフとする。
|V(G)| ≦ 2 であればあきらかなので |V(G)| ≧ 3 としてよい。
どの点の次数も 6 以上だとすると
2|E(G)| = Σv∈V(G) deg(v) ≧ 6|V(G)| ∴ 3|V(G)| ≦ |E(G)|
これは |V(G)| ≧ 3 の単純平面グラフ G に対して |E(G)| ≦ 3|V(G)| - 6 という結果に反する。
３． 頂点数が４以上のどんな単純平面グラフも次数が 5 以下の頂点を４個以上持つことを示せ。
＜Sol＞ いくつか辺を付加して各面が外面も含めて３角形的であるようにできる。そのグラフ G に次数が 5 以下の頂点が４個以上あることを示せばよい。
G の頂点数，辺数，面数をそれぞれ n, e, f とすると、2e = 3f であるからオイラーの公式 v - e + f = 2 により頂点の次数の総和 2e は 6n - 12 であることがわかる。
次数が 6 未満の頂点についての 6 - deg(v) の総和は少なくとも 12 であることになるが δ(G) ≧ 3 （なぜ？）なので各項はせいぜい 3 だけ寄与するのでそのような頂点は４個以上あることになる。
４． Petersen グラフ（ → １章演習問題５ ）は平面的でないことを示せ。
＜Sol＞ 平面的グラフを縮約しても平面的である。（なぜ？）
Petersen グラフは縮約により K5 にできるが K5 は非平面的なので Petersen グラフも非平面的であることになる。
【 NOTE 】 平面的グラフを縮約しても平面的であることは、たとえば平面グラフとして実現しておくと双対グラフでは辺の除去を繰り返しても平面グラフであることから言える。
＜別解＞ Petersen グラフの内周は 5 であることから 5f ≦ 2ε．
よって、もしも Petersen グラフが平面的だとすると、これとオイラーの公式から ε ≦ (5/3)(ν - 2) すなわち 15 ≦ (5/3)(10 - 2) となり不合理。
５． グラフ G について次は同値であることを証明せよ。（ Wagner ）
（１） 平面的．
（２） K5 も K3,3 もマイナーとして含まない。
＜Sol＞ (1)⇒(2)． 平面的グラフに辺の除去や縮約もしくは孤立点の除去を何回か施しても平面的なので K5 も K3,3 もマイナーとなりえない。
(2)⇒(1)． 非平面的とすると Kuratowski の定理により K5 の細分もしくは K3,3 の細分を含む。
それに含まれない辺を除去して行って孤立点も除去して行って次数が２の点に接合している辺を縮約して行くことにより K5 もしくは K3,3 がえられるので K5 もしくは K3,3 がマイナーとして含まれていたことになる。
第１１章
１． ループをもたないグラフ G に対して不等式 χ(G) ≦ (1/2)(1 + √(1 + 8ε)) が成り立つことを証明せよ。
＜Sol＞ V(G) の k = χ(G) 個の独立集合への分割が存在する。
ある２つの独立集合が辺で結ばれてないとするとそれらを合併しても独立集合となり染色数が k 未満であることになってしまうから、どの２つの独立集合も少なくともひとつの辺で結ばれていることになる。
∴ ε ≧ k(k - 1)/2 ∴ k ≦ (1/2)(1 + √(1 + 8ε))
２． グラフ G のどの２つの奇サーキットも頂点を共有するとき χ(G) ≦ 5 であることを示せ。
＜Sol＞ 奇サーキットをもたなければ χ(G) ≦ 2 で成立するので G は奇サーキットをもつとしてよい。
C を最短の奇サーキットとする。
χ(G - V(C)) ≧ 3 であれば C と頂点を共有しない奇サーキットが存在することになってしまうから χ(G - V(C)) ≦ 2 である。
C が最短の奇サーキットであることから C 上の２点を結ぶ辺で C の辺でないのは存在しない（なぜ？）ので χ(＜C＞) = 3 である。
よって、これらの染色を合わせて χ(G) ≦ 5 をえる。
＜別解＞ χ(G) ≧ 6 とし、1, 2, 3, . . . による最小色の染色を考える。
色 1, 2, 3 で染色された頂点で誘導される部分グラフは奇サーキットをもつ。また、色 4, 5, 6 で染色された頂点で誘導される部分グラフも奇サーキットをもつ。
これら２つの奇サーキットは頂点を共有しないことになり不合理。
３． グラフ G について次は同値であることを証明せよ。
（１） ２部グラフである．
（２） どの部分グラフ H に対しても H の頂点の半分以上が独立．
＜Sol＞ (1)⇒(2)． ２部グラフの部分グラフも２部グラフで、部集合のうちサイズの大きいほうが題意の独立集合となる。
(2)⇒(1)． G が２部グラフでないとすると奇サーキット C をもつ。
H = ＜C＞ とすると、H の頂点で独立なのは半分未満しかとれない。
４． Blanusa スナーク、フラワースナークがたしかにスナークであることを確めよ。
５． χ(G) = r ならば G は Kr をマイナーとしてもつ、という予想（Hadwiger 予想）がある。この予想が r = 1, 2, 3, 4 のとき成り立つことを示せ。
＜Sol＞ r = 1 のとき. χ(G) = 1 というのは G が孤立点のみからなることなのであきらか。
r = 2 のとき. χ(G) = 2 というのは G がリンクをもつ２部グラフということであきらか。
r = 3 のとき. K3 をマイナーとしてもたないとすると G は森もしくはそのいくつかの辺を多重辺にしたもので χ(G) ≦ 2 である。
r = 4 のとき.（ by Dirac ） G の部分グラフ H で χ(H) = 4 でどの H の頂点 v についても χ(H - v) = 3 であるのが存在する。
H は切断点をもたず各頂点の次数は３以上であることが背理法によって容易に示される。
C を H における最長のサーキットとする。C の長さは４以上である。
C における非隣接な２点をむすぶ H におけるパスでその両端点以外は C 上にないのをとりあえず C パスとよぶことにする。
どの C の頂点も他のある C の頂点と C パスで結ばれている。
（∵） v を C の頂点、u と w を C における v の２つの隣接点とする。
deg(v)≧3 ゆえ v は u, w 以外の隣接点 x をもつ。
x が C の頂点であれば vx でＯＫ。
x が C の頂点でないとき. H が切断点をもたないことから x から w への v を通らないパス π が存在する。C の最長性から π が最初に C とぶつかる頂点 P は u, w ではない。vx ∪ π(x, P) は C パスである。 //
あとはこのことから場合分けによって H は K4 の細分を含むことがわかる。
【 NOTE 】 Hadwiger 予想は χ(G) = r を χ(G) ≧ r としても同値である。（なぜ？）
r = 5 のときの Hadwiger 予想から４色定理が帰結される。
（∵） どんなブリッジをもたない平面グラフも 4 彩色できる、の双対で、どんなループをもたない平面グラフも 4 染色できる、を示せばよい。
χ(G) ≧ 5 とすると K5 をマイナーとしてもつことになり平面グラフでないことになる。 //
Wagner は逆に４色定理から r = 5 のときの Hadwiger 予想が帰結されることを示した。
r = 6 の場合が Seymour のグループによって証明された。
第１４章
１． 有向グラフについて、強連結であることとかってな V の空でない真部分集合に対してそれを出る弧が存在することは同値であることを証明せよ。
＜Sol＞ ⇒． あきらか。
逆． かってな V の空でない真部分集合に対してそれを出る弧が存在するが強連結でないとする。すると、ある頂点 v と u があって v から u へのパスが存在しないことになる。
集合 Vv = { w∈V | v から w へのパスがある } は v を含み u を含まないので V の空でない真部分集合である。
仮定により Vv を出る弧 v'w が存在するが Vv の定義より v から v' へのパスが存在するので v から w へのパスが存在することになって矛盾する。
２． 奇サーキットをもつグラフの強連結な向き付けは奇有向サーキットを含むことを示せ。
＜Sol＞ D を奇サーキット v1 v2 . . . v2k+1 をもつグラフ G の強連結な向き付けとする。
D が強連結であることから各 i について vivi+1 パスが存在する。
もしもある i があってどの vivi+1 パスも長さが even とすると辺 vivi+1 は vi+1 から vi に向き付けされていることになるから (vi+1, vi) を通る奇有向サーキットが存在することになる。
そうでないとき． 各 i についての長さが odd の vivi+1 パスを 2k + 1 の奇数個つないだものは奇有向サーキットを含んでいる。
３． 入次数が 0 の頂点をもたないトーナメント T はキングを３個以上もつことを証明せよ。
＜Sol＞ T のキングのひとつを x とする。
＜N-(x)＞ もトーナメントであるから ＜N-(x)＞ のキング y が存在するが y は T においてもキングであることがわかる。
同様にして ＜N-(y)＞ にも T のキング z が存在する。
x は ＜N-(y)＞ に属さないから z ≠ x で x, y, z は異なるキングであることになる。
４． Cayley の定理を行列木定理から導け。
＜Sol＞ |L1(Kn)| は
５． τ(Km , n) = mn - 1 nm - 1 を示せ。
＜Sol＞ ４と同様にして示せる。
６． P(G; k) の ν(G) - 1 次の係数は -ε(G) であることを示せ。
＜Sol＞ 染色多項式のところの定理の証明と同じ記号を使うことにする。
帰納的に
(ν(G) - 1 次の係数) = - (ap-1 + 1)
= - ((ε - 1) + 1)
= - ε
７． ν(G) = n のグラフ G について次は同値であることを証明せよ。
（１） 木である。
（２） P(G; k) = k (k - 1)n - 1．
＜Sol＞
(1)⇒(2) G のひとつの頂点 v は k 通りに染色できる。また、v から離れて行くと出会う頂点には手前の頂点と異なる k - 1 通りの染色ができる。
よって、P(G; k) = k (k - 1)n - 1 をえる。
(2)⇒(1) 染色多項式は各成分の染色多項式の積で、染色多項式の定数項は 0 なので G は連結であることがわかる。
k (k - 1)n - 1 を展開した kn - 1 の係数は - (n - 1) ゆえ前問より G の辺数は n - 1 である。
連結グラフで頂点数 n ，辺数 n - 1 だから木であることになる。
８． n 頂点を持つサーキット Cn について T(Cn; x, y) = xn - 1 + xn - 2 + . . . + x + y であることを示せ。
＜Sol＞ n = 1 のとき T(C1; x, y) = y T(K1; x, y) = y で成立。
n - 1 で成り立つと仮定。
T(Cn; x, y) = T(Pn; x, y) + T(Cn - 1; x, y)
= xn - 1 + (xn - 2 + xn - 3 + . . . + x + y)
よって n のとき成立。
９． 単純な連結平面的グラフは各辺が直線分であるように平面に辺が交差しないように描画できることを示せ。（ Wagner, Fary ）
＜Sol＞ 頂点数が 1, 2, 3 のときはあきらかなので 4 以上とする。
必要ならいくつか辺を付加して単純で各面が外面も含めて３角形的であるように描画できる。
そのようなグラフは 3 連結（なぜ？）なので凸描画でき元のグラフは題意のように描画できることになる。
【 NOTE 】
＜Sol＞ ←G→ の頂点集合は [n] とする。
２つの完全マッチング M, M' に対して、＜M ∪ M'＞ の成分は K2 か長さが偶数のサーキットである（第７章演習の１）から K2 のところはその辺で決まる長さ２のサーキットにし長さが偶数のサーキットのところはその上の頂点で最小なのから番号の若い頂点の方に向き付けすることにより ←G→ の偶サーキット被覆が定まる。
この対応は全単射である。
