10.1.11#

$G$ を単純グラフとします。$G$ の頂点の集合上の関係 $R$ を次のように定義します：$uRv$ であるのは、$\{u, v\}$ に関連付けられた辺が存在するとき、かつそのときに限ります。 このとき、$R$ が $G$ 上の対称的で反射性を持たない関係であることを示しなさい。

$R$ が対称的であることを示します。もし $uRv$ であれば、$\{u, v\}$ に関連付けられた辺が存在します。 そして、集合 $\{u, v\} = \{v, u\}$ であるため、この辺は $\{v, u\}$ にも関連付けられます。したがって、$vRu$ が成立します。このことから、定義により $R$ は対称的な関係です。

次に、$R$ が反射性を持たないことを示します。単純グラフでは自己ループが許されないため、$uRu$ は決して成立しません。このことから、定義により $R$ は反射性を持たない関係です。

10.1.12#

$G$ をすべての頂点に自己ループを持つ無向グラフとします。$G$ の頂点の集合上の関係 $R$ を次のように定義します：$uRv$ であるのは、$\{u, v\}$ に関連付けられた辺が存在するとき、かつそのときに限ります。 このとき、$R$ が $G$ 上の対称的で反射的な関係であることを示しなさい。

$R$ が対称的であることを示します。もし $uRv$ であれば、頂点 $u$ と $v$ を結ぶ辺が存在します。グラフが無向であるため、この辺は同時に頂点 $v$ と $u$ を結びます。 したがって、$vRu$ が成立します。このことから、$R$ は対称的な関係です。

次に、$R$ が反射的であることを示します。すべての頂点に自己ループが存在するため、任意の頂点 $u$ に対して $uRu$ が成立します。このことから、$R$ は反射的な関係です。

ハンドシェイク定理 (握手補題)#

$G = (V, E)$ を辺が $m$ 本ある無向グラフとします。このとき、

が成り立ちます。

証明:
無向グラフの各辺はちょうど2つの頂点に付随しており、それぞれの頂点の次数に寄与します。 したがって、すべての頂点の次数の和はグラフ内の辺の数を2倍したものになります。このことから、式 $2m = \sum_{v \in V} \mathrm{deg}(v)$ が成立します。これは、重辺や自己ループが存在する場合にも適用されます。

10.2 定理2#

無向グラフでは、奇数次数の頂点の数は偶数である。

証明:
$V_1$ を偶数次数の頂点の集合、$V_2$ を奇数次数の頂点の集合とします。無向グラフ $G = (V, E)$ において、$m$ を辺の数とすると次が成り立ちます：

$v \in V_1$ の場合、$\mathrm{deg}(v)$ は偶数なので、右辺の最初の項は偶数になります。また、式全体が $2m$（偶数）であるため、右辺の2つの項の和も偶数になります。 したがって、右辺の第2項 $\sum_{v \in V_2} \mathrm{deg}(v)$ も偶数でなければなりません。

$V_2$ に含まれるすべての次数 $\mathrm{deg}(v)$ は奇数であるため、その和が偶数であるには、奇数項の数が偶数でなければなりません。したがって、奇数次数の頂点の数は偶数です。

10.2 定理3#

$G = (V, E)$ を有向辺を持つグラフとします。このとき、

が成り立ちます。

証明:
各辺には始点（初期頂点）と終点（終端頂点）が存在するため、すべての頂点の入次数の和と出次数の和は等しくなります。これらの和はいずれもグラフに存在する辺の総数 $|E|$ に等しいことが示されます。

10.2 定理4#

単純グラフが二部グラフであるのは、隣接する2つの頂点が同じ色に塗られないように、グラフの各頂点に2つの異なる色のいずれかを割り当てることが可能である場合、かつその場合に限ります。

証明:
まず、$G = (V, E)$ が二部グラフであると仮定します。 このとき、$V = V_1 \cup V_2$ であり、$V_1$ と $V_2$ は互いに頂点集合であり、$E$ の各辺は $V_1$ の頂点と $V_2$ の頂点を結びます。 $V_1$ の各頂点に1つ目の色を、$V_2$ の各頂点に2つ目の色を割り当てると、隣接する2つの頂点が同じ色になることはありません。

次に、グラフの頂点に2色を割り当て、隣接する2つの頂点が同じ色に塗られないようにすることが可能であると仮定します。 このとき、1つ目の色が割り当てられた頂点の集合を $V_1$、2つ目の色が割り当てられた頂点の集合を $V_2$ とします。 このとき、$V_1$ と $V_2$ は互いに頂点集合であり、$V = V_1 \cup V_2$ となります。 また、隣接する頂点が同じ集合に属することはないため、各辺は $V_1$ の頂点と $V_2$ の頂点を結びます。したがって、$G$ は二部グラフです。

Hallの結婚定理#

二部グラフ $G = (V, E)$ が分割 $(V_1, V_2)$ を持つとします。 このとき、$V_1$ から $V_2$ への完全マッチングが存在するのは、任意の $V_1$ の部分集合 $A$ に対して、次の条件が満たされる場合、かつその場合に限ります：

証明:

必要条件 ($|N(A)| \geq |A|$) を示す部分:
まず、$V_1$ から $V_2$ への完全マッチング $M$ が存在すると仮定します。 このとき、任意の $A \subseteq V_1$ に対して、各 $v \in A$ はマッチング $M$ の辺によって $V_2$ の頂点に接続されます。 したがって、$N(A)$ の頂点数は少なくとも $A$ の頂点数に等しいか、それ以上である必要があります。つまり、$|N(A)| \geq |A|$ が成り立ちます。

十分条件 ($|N(A)| \geq |A|$) を示す部分:
ここでは、$|N(A)| \geq |A|$ がすべての $A \subseteq V_1$ に対して成り立つと仮定し、 このとき $V_1$ から $V_2$ への完全マッチング $M$ が存在することを示します。これを示すために、$|V_1|$ に関する数学的帰納法を用います。

• 基底の場合:
  $|V_1| = 1$ とします。この場合、$V_1$ は1つの頂点 $v_0$ を含みます。 このとき、$|N(\{v_0\})| \geq |\{v_0\}| = 1$ であるため、少なくとも1つの頂点 $w_0 \in V_2$ が $v_0$ に接続されています。この接続により完全マッチングが得られます。

• 帰納ステップ:
  $|V_1| = k$ のとき、完全マッチングが存在することを仮定します。次に、$|V_1| = k+1$ の場合を示します。
  この場合、帰納的仮定を用いるために2つのケースを考えます。

  • ケース (i):
    $V_1$ の任意の部分集合 $A$ ($1 \leq |A| \leq k$) に対して、$A$ の各頂点が少なくとも $|A|+1$ 個の $V_2$ の頂点に接続されていると仮定します。 このとき、任意の $v \in V_1$ を取り除いたグラフ $H' = (V_1 \setminus \{v\}, V_2 \setminus \{w\})$ を構成し、帰納法により $H'$ には完全マッチングが存在することを示します。

  • ケース (ii):
    ある $j$ ($1 \leq j \leq k$) に対して、$V_1$ の部分集合 $A$ が $V_2$ にちょうど $j$ 個の隣接頂点を持つ場合を考えます。 このとき、帰納的仮定を適用し、$A$ とその隣接頂点を削除したグラフにも完全マッチングが存在することを示します。

この2つのケースを考慮することで、いずれの場合にも完全マッチングが存在することを示すことができます。

したがって、$|N(A)| \geq |A|$ が任意の $A \subseteq V_1$ に対して成り立つ場合、$V_1$ から $V_2$ への完全マッチングが存在することが証明されました。

10.2.6#

パーティーにいる人々の集合において、各人が握手をした人数を足し合わせた合計が偶数であることを示しなさい。ただし、自分自身と握手することはないものとします。

証明:
この問題をグラフとしてモデル化します。パーティーにいる人々をグラフの頂点とし、握手をした2人の間に辺を引きます。このとき、各頂点の次数はその頂点が表す人が握手をした人数に対応します。

定理1（握手定理）によれば、グラフ内のすべての頂点の次数の和は偶数です（これは $2e$、すなわち辺の数を2倍した値に等しいため）。したがって、握手をした人数の合計も偶数であることが示されます。

10.2.18#

少なくとも2つの頂点を持つ単純グラフでは、次数が同じ頂点が必ず2つ存在することを示しなさい。

証明:
この問題はセクション6.2の演習42と本質的に同じであり、そこでグラフが「互いに知り合いである」という関係をモデル化しています。

各人が知っている人数はグラフにおける対応する頂点の次数に等しいと考えます。次のように証明します：

1. 単純グラフの頂点数を $n$ とします（$n \geq 2$）。
2. 各頂点の次数の可能な値は $0, 1, \ldots, n-1$ ですが、ある1人が他の全員を知っている場合（次数 $n-1$）、他の誰かが誰も知らない（次数 $0$）という状況は対称性の仮定より不可能です。
3. したがって、可能な次数の値は $n$ 個ではなく最大で $n-1$ 個です。
4. しかし、頂点の数は $n$ なので、鳩の巣原理（Pigeonhole Principle）によって少なくとも2つの頂点が同じ次数を持つ必要があります。

これにより、少なくとも2つの頂点が同じ次数を持つことが証明されました。

10.2.36#

$n$ を正の整数とします。完全グラフ $K_n$ の頂点集合の非空部分集合によって誘導される部分グラフが完全グラフであることを示しなさい。

証明:
完全グラフ $K_n$ では、任意の2頂点が隣接しています。したがって、頂点集合の非空部分集合によって誘導される部分グラフにおいても、その部分集合内の任意の2頂点は隣接しています。これにより、誘導部分グラフが完全グラフであることが示されます。

10.2.66#

もし $G$ が頂点数 $v$、辺数 $e$ を持つ二部単純グラフであるならば、

$$e \leq \frac{v^2}{4}$$

が成り立つ。

証明:

二部グラフ $G$ を構成する2つの部分のサイズを $k$ と $v - k$ とする。このとき、異なる部分間の各頂点対の間に辺を持つ場合、辺の最大数は

で表される。

関数 $f(k) = k(v - k)$ の最大値を求めると、代数的手法または微分計算により、最大値は $k = \frac{v}{2}$ のときに達成されることが分かる。このとき、

となる。

したがって、辺の数 $e$ は最大でも $\frac{v^2}{4}$ である。

10.4 定理1#

連結無向グラフの任意の2つの異なる頂点の間には単純な経路(パス)が存在する。

証明:
$G = (V, E)$ を連結無向グラフとし、$u$ と $v$ を $G$ の2つの異なる頂点とします。$G$ が連結であるため、$u$ と $v$ の間には少なくとも1つの経路が存在します。

この経路の中で最短のものを選び、その頂点列を $x_0, x_1, \ldots, x_n$ とします。ただし、$x_0 = u$ かつ $x_n = v$ です。この最短経路が単純であることを示します。

仮にこの経路が単純でないとすると、ある $i$ と $j$ ($0 \leq i < j$) に対して $x_i = x_j$ となるような部分が存在します。 この場合、$x_i$ と $x_j$ の間の頂点列を削除した経路 $x_0, x_1, \ldots, x_{i-1}, x_j, \ldots, x_n$ を構成することで、より短い経路を得ることができます。これは最短経路の仮定に矛盾します。

したがって、最短経路は単純である必要があります。このことから、任意の2つの異なる頂点の間には単純な経路が存在することが示されました。

10.4 定理2（隣接行列と経路(歩道)の関係）#

グラフ $G$ を、その頂点の順序 $v_1, v_2, \ldots, v_n$ に対応する隣接行列 $A$ を持つグラフとします（有向または無向の辺を持ち、多重辺やループも許容）。 $v_i$ から $v_j$ への長さ $r$ の異なる経路(歩道)の数は、行列 $A^r$ の $(i, j)$ 成分に等しい。

証明:
この定理を数学的帰納法によって証明します。

1. 基底の場合 ($r = 1$):
   長さ1の経路とは、単一の辺を意味します。このとき、$v_i$ から $v_j$ への長さ1の経路の数は、隣接行列 $A$ の $(i, j)$ 成分 $a_{ij}$ に対応します。よって、定理は成立します。

2. 帰納ステップ ($r \to r+1$):
   $r$ に対して、$A^r$ の $(i, j)$ 成分が $v_i$ から $v_j$ への長さ $r$ の経路の数を表していると仮定します（帰納法の仮定）。

   行列 $A^{r+1} = A^r \cdot A$ を考えます。このとき、$A^{r+1}$ の $(i, j)$ 成分は次のように計算されます：

   $$(A^{r+1})_{ij} = \sum_{k=1}^n b_{ik} a_{kj},$$

   ただし、$b_{ik}$ は $A^r$ の $(i, k)$ 成分であり、$b_{ik}$ は $v_i$ から $v_k$ への長さ $r$ の経路の数を表しています（帰納法の仮定より）。

   長さ $r+1$ の経路は、長さ $r$ の経路である $v_i$ から $v_k$ への経路に、$v_k$ から $v_j$ への長さ1の辺を追加することで構成されます。 この数をすべての中間頂点 $v_k$ にわたって合計すると、$v_i$ から $v_j$ への長さ $r+1$ の経路の総数が得られます。

   よって、$A^{r+1}$ の $(i, j)$ 成分は、$v_i$ から $v_j$ への長さ $r+1$ の経路の数を表します。

以上より、帰納法により定理が示されました。

10.4.18#

強連結成分内の2つの頂点を結ぶ有向経路上に訪れるすべての頂点も、同じ強連結成分に属することを示しなさい。

証明:
有向経路を $a, b, c, \ldots, z$ とします。ここで、$a$ と $z$ は同じ強連結成分に属していると仮定します。この仮定により、$z$ から $a$ への有向経路が存在します。 この経路を元の経路 $a, b, c, \ldots, z$ に加えることで、閉路が形成されます。

この閉路を使うことで、元の経路上の任意の頂点から他の任意の頂点に到達することが可能になります。したがって、元の経路上のすべての頂点は同じ強連結成分に属していることが示されます。

10.4.28#

$n$ 頂点を持つ任意の連結グラフは、少なくとも $n-1$ 本の辺を持つことを示しなさい。

証明:
数学的帰納法を用いて証明します。

1. 基底の場合 ($n = 1$):
   頂点が1つしかない場合、連結グラフには辺が存在しません。このとき、辺の本数は $n - 1 = 0$ となり、命題が成り立ちます。

2. 帰納ステップ ($n \to n+1$):
   $n$ 頂点を持つ連結グラフは少なくとも $n-1$ 本の辺を持つと仮定します（帰納法の仮定）。
   $n+1$ 頂点を持ち、$n$ 本未満の辺を持つ連結グラフ $G$ を仮定します。

   • グラフ $G$ の頂点の次数の和は $2e$（$e$ は辺の本数）に等しいため、頂点の次数の和は $2n$ 未満です。
   • 頂点の数は $n+1$ であるため、少なくとも1つの頂点の次数は $2$ 未満でなければなりません。
   • グラフが連結であるため、この頂点は孤立しておらず、次数はちょうど $1$ です。この頂点とその接続された辺を削除すると、残りのグラフは $n$ 頂点を持ち、辺の数は $n-1$ 未満になります。

   帰納法の仮定により、これは矛盾を引き起こします。したがって、$n+1$ 頂点を持つ連結グラフは少なくとも $n$ 本の辺を持たなければなりません。

以上より、任意の $n$ 頂点を持つ連結グラフは少なくとも $n-1$ 本の辺を持つことが示されました。

10.4.29#

単純グラフ $G = (V, E)$ を考えます。頂点 $V$ 上の関係 $R$ を、頂点の組 $(u, v)$ が $u = v$ または $u$ から $v$ への経路が存在する場合に成立するものと定義します。 このとき、$R$ が同値関係であることを示しなさい。

証明:
関係 $R$ が同値関係であることを示すために、以下の3つの性質を確認します：反射性、対称性、推移性。

1. 反射性:
   任意の頂点 $u \in V$ に対して、$u$ から自身への経路は存在します（長さ0の経路）。したがって、$(u, u) \in R$ が成立します。よって、$R$ は反射的です。

2. 対称性:
   $(u, v) \in R$ と仮定します。このとき、$u$ から $v$ への経路が存在します。この経路を逆向きにたどることで、$v$ から $u$ への経路が得られます。 したがって、$(v, u) \in R$ が成立します。よって、$R$ は対称的です。

3. 推移性:
   $(u, v) \in R$ および $(v, w) \in R$ と仮定します。 このとき、$u$ から $v$ への経路と $v$ から $w$ への経路を連結することで、$u$ から $w$ への経路が得られます。 したがって、$(u, w) \in R$ が成立します。よって、$R$ は推移的です。

以上より、関係 $R$ は反射性、対称性、推移性を満たすため、同値関係であることが示されました。

10.4.30#

任意の単純グラフにおいて、奇数次数を持つ任意の頂点から他の奇数次数の頂点への経路が存在することを示しなさい。

証明:
$v$ を奇数次数を持つ頂点とします。$H$ を、グラフ $G$ のうち $v$ を含む連結成分とします。この $H$ 自体もグラフであり、ハンドシェイク定理によれば、任意のグラフは奇数次数の頂点を偶数個持つ必要があります。 したがって、$H$ 内には $v$ を除いて少なくとも1つ別の奇数次数の頂点 $w$ が存在します。

さらに、$H$ は連結であるため、定義より $v$ から $w$ への経路が存在します。以上より、奇数次数の頂点から他の奇数次数の頂点への経路が存在することが証明されました。

10.4.35#

$v$ がカットエッジの端点であるとします。このとき、$v$ がペンダント頂点でない場合に限り、カット頂点であることを示しなさい。

証明:
ペンダント頂点（次数1の頂点）は明らかにカット頂点ではありません。したがって、カットエッジの端点でカット頂点であるものはペンダント頂点ではありません。

カットエッジを削除すると、元のグラフの連結成分の数よりも多くの連結成分を持つグラフが生成されます。もしカットエッジの端点がペンダント頂点でない場合、その端点を含む連結成分には他の頂点が存在します。このとき、その頂点 $v$ とその頂点に接続するすべての辺を削除すると、元のカットエッジを含むすべての辺が削除されるため、元のグラフの連結成分の数よりもさらに多くの連結成分を持つグラフが生成されます。

したがって、カットエッジの端点でペンダント頂点でないものはカット頂点です。

10.4.36#

連結単純グラフ $G$ において、ある頂点 $c$ がカット頂点であることと、$c$ とは異なる頂点 $u$ と $v$ が存在し、 $u$ と $v$ のすべての経路が $c$ を通ることが同値であることを示しなさい。

証明:
まず、$c$ がカット頂点である場合を考えます。この場合、$c$ を削除すると、グラフの連結成分の数が増加します。 したがって、$c$ を削除した後、異なる連結成分に属する2つの頂点 $u$ と $v$ が存在します。このような $u$ と $v$ の間のすべての経路は $c$ を通る必要があります。

逆に、$u$ と $v$ のすべての経路が $c$ を通る場合を考えます。このとき、$c$ を削除すると $u$ と $v$ は異なる連結成分に属することになります。 したがって、$c$ を削除すると少なくとも2つの連結成分が生成されるため、$c$ はカット頂点です。

これにより、カット頂点の条件と経路条件が同値であることが示されました。

10.4.37#

少なくとも2つの頂点を持つ単純グラフには、カット頂点でない頂点が少なくとも2つ存在することを示しなさい。

証明:
仮に、カット頂点でない頂点が高々1つしか存在しないと仮定します。 この場合、グラフ $G$ の頂点 $u$ と $v$ の距離（最短経路の長さ）を $d(u, v)$ とし、$d(u, v)$ が最大となる2つの頂点 $s$ と $t$ を取ります。 このとき、$s$ または $t$（またはその両方）はカット頂点である必要があります。

$s$ をカット頂点と仮定し、$s$ を削除して得られるグラフの連結成分の1つに属する頂点 $w$ を考えます。 この場合、$w$ から $t$ へのすべての経路は $s$ を通らなければなりません。これにより、$d(w, t) > d(s, t)$ となりますが、これは $d(s, t)$ が最大であるという仮定に矛盾します。

したがって、カット頂点でない頂点は少なくとも2つ存在しなければなりません。

10.4.38#

単純グラフにおいて、ある辺がカットエッジであることと、その辺が単純な閉路の一部でないことが同値であることを示しなさい。

証明:

1. カットエッジである場合:
   $e = \{u, v\}$ をカットエッジと仮定します。この場合、$e$ を削除すると、$u$ と $v$ の間に経路が存在しなくなり、グラフの連結性が失われます。 したがって、$u$ と $v$ を結ぶ経路は $e$ を必ず含む必要があります。
   $e$ を含む任意の閉路において、$u$ から $v$ への経路と $v$ から $u$ への経路の両方が $e$ を使用しなければならないため、$e$ が2回出現することになります。したがって、この閉路は単純ではありません。

2. 単純な閉路の一部でない場合:
   $e = \{u, v\}$ が単純な閉路の一部でないと仮定します。この場合、$e$ を削除しても、$u$ と $v$ の間には少なくとも1つの経路が残ります。 このため、$e$ を削除してもグラフの連結性は失われません。したがって、$e$ はカットエッジではありません。

これらの結果より、ある辺がカットエッジであることと、その辺が単純な閉路の一部でないことが同値であることが示されました。

10.4.45#

頂点数が $n$ の単純グラフ $G$ が $(n-1)(n-2)/2$ 本を超える辺を持つ場合、$G$ が連結であることを示しなさい。

証明:
仮定として、グラフ $G$ が連結でないとします。この場合、$G$ は複数の連結成分を持ち、各成分の頂点数を考慮して、最大の辺の数を計算します。

1. 連結成分の頂点数を分割:
   $G$ の1つの連結成分が $k$ 頂点を持つと仮定します（$1 \leq k \leq n-1$）。残りの $n-k$ 頂点が別の成分を形成するとします。

2. 各成分での最大辺数:
   頂点数 $k$ の完全グラフの辺数は $\binom{k}{2} = k(k-1)/2$ であり、 同様に $n-k$ 頂点の完全グラフの辺数は $\binom{n-k}{2} = (n-k)(n-k-1)/2$ です。

   $G$ が持つことができる最大の辺の総数は次のようになります：

   $$E_{\max} = \frac{k(k-1)}{2} + \frac{(n-k)(n-k-1)}{2}.$$

3. 2次関数として解析:
   上記の式を簡単化すると次のようになります：

   $$f(k) = \frac{k^2 - k + (n-k)^2 - (n-k)}{2} = \frac{k^2 - nk + n^2 - n}{2}.$$

   この式は $k$ に関する2次関数です。

4. 最大値の評価:
   この関数は $k = 1$ または $k = n-1$ で最大値をとります。これらの場合、$f(k)$ は次のようになります：

   $$f(1) = \frac{(n-1)(n-2)}{2}.$$

   よって、連結でないグラフが持つ辺の数は高々 $(n-1)(n-2)/2$ です。

5. 結論:
   $G$ が $(n-1)(n-2)/2$ 本を超える辺を持つ場合、$G$ は必ず連結でなければなりません。

これにより命題が証明されました。

10.4.51#

もし $G$ が連結グラフであるならば、$G$ が完全グラフでない場合に限り、頂点を削除することで $G$ を非連結にすることができる。

証明:

（必要条件）
もし $G$ が完全グラフであるならば、頂点を1つずつ削除しても、各ステップで残るグラフは依然として完全グラフである。このため、どの時点でも $G$ は非連結にならない。

（十分条件）
逆に、もし $G$ から辺 $uv$ が欠けている場合、$G$ は完全グラフではない。このとき、$u$ と $v$ を除く全ての頂点を削除すると、残るグラフは $u$ と $v$ のみから構成され、両者の間に辺が存在しないため、非連結になる。

したがって、$G$ が完全グラフでない場合、頂点を削除して $G$ を非連結にすることが可能である。

10.4.55#

グラフ $G$ において、

$$\kappa(G) \leq \lambda(G)$$

が成り立つことを示せ。

証明:

$G$ を $n$ 個の頂点を持つグラフとする。このとき、$\kappa(G) \leq n - 1$ である。
$C$ を $G$ の最小の辺カットとし、頂点集合 $S$ を $G$ の頂点集合 $V$ の補集合 $S' = V - S$ から切り離す非空の部分集合とする。

もし任意の $x \in S$ と $y \in S'$ に対して $xy$ が $G$ の辺であるならば、カット集合 $C$ のサイズは $|S||S'|$ となる。 この値は少なくとも $n - 1$ であるため、$\kappa(G) \leq \lambda(G)$ が成り立つ。

そうでない場合、$x \in S$ と $y \in S'$ が非隣接頂点であると仮定する。このとき、集合 $T$ を以下のように定義する：$S$ の全ての隣接頂点と $S'$ 内の $x$ の隣接頂点から構成される。 さらに、$x$ を除く $S$ の頂点全てを追加する。

集合 $T$ は $x$ と $y$ を分離する頂点カットであり、このカットが $S$ と $S'$ を分離する。 今度は、$T \cap S$ から $S'$ への辺、および $T \cap S$ の各頂点から $S'$ への1つの辺を考える。このような辺の集合は $|T|$ 個の辺を形成する。

このことから、次が成り立つ：

したがって、$\kappa(G) \leq \lambda(G)$ が示された。

10.4.59#

単純グラフ $G$ において、頂点 $u$ と $v$ の間に同じ辺の集合を含まない2つの単純パス $P_1$ と $P_2$ が存在すると仮定する。このとき、$G$ に単純閉路（サイクル）が存在することを示せ。

証明:

単純パス $P_1$ と $P_2$ をそれぞれ

および

とする。これらのパスは同じ頂点 $u$ から始まるが、同じ辺の集合を含まないと仮定されているため、いずれかの時点で分岐する必要がある。

分岐が $P_1$ または $P_2$ の終了後にのみ発生する場合、残りのもう一方のパスが $v$ から $v$ への単純閉路を形成する。一方、次のように仮定できる：

だが

単純閉路を構成するために、パス $y_i, y_{i+1}, y_{i+2}, \ldots$ をたどり、最初に $P_1$ 上の頂点に再び遭遇するまで進む（これは $y_{i+1}$ 以上、遅くとも $y_m$ までには発生する）。 その後、$P_1$ 上を前方または後方に進むことで、再び $x_i$ に戻る。このプロセスにより閉路が形成される。

$x_i = y_i$ であるため、確かに閉路が形成される。この閉路は単純である。なぜなら、$P_1$ と $P_2$ が単純であるという仮定より、$x_k$ や $y_l$ の間で辺の重複がないことが保証される。 また、$P_2$ から $P_1$ に切り替えた時点で、既に使用した $y_l$ の辺が $x_k$ のいずれかと等しくなることはないためである。

したがって、$G$ には単純閉路が存在することが示された。

10.4.63#

単純グラフ $G$ が二部グラフであるのは、奇数本の辺を持つ閉路を持たない場合、かつその場合に限ることを示しなさい。

証明:

1. $G$ が二部グラフである場合:
   $G$ を二部グラフと仮定し、その二部集合を $A$ と $B$ とします。二部グラフでは、すべての経路は $A$ と $B$ の頂点を交互に通ります。 したがって、経路の長さが奇数であれば $A$ で始まり $B$ で終わり、長さが偶数であれば $A$ で始まり再び $A$ で終わります。

   閉路は開始頂点と終了頂点が同一であるため、閉路の長さは必ず偶数になります。したがって、二部グラフ $G$ は奇数本の辺を持つ閉路を持ちません。

2. $G$ が奇数本の辺を持つ閉路を持たない場合:
   $G$ が奇数本の辺を持つ閉路を持たないと仮定します。この場合、次の手順で $G$ が二部グラフであることを示します：

   • グラフが連結でない場合、各連結成分について個別に検討すればよいので、連結グラフを仮定してよい。
   • $G$ の任意の頂点 $v$ を選び、$A$ を $v$ から奇数長の経路で到達可能な頂点集合、$B$ を $v$ から偶数長の経路で到達可能な頂点集合と定義します。
   • $G$ の連結性から、すべての頂点は $A$ または $B$ のいずれかに属します。
   • もしある頂点が $A$ と $B$ の両方に属するならば、ある奇数長の経路と偶数長の経路を結合して奇数長の閉路を構成することができ、仮定に矛盾します。

   さらに、任意の辺 $xy$ について、$x \in A$ の場合、$x$ から $y$ への経路は偶数長となり、$y$ は $B$ に属します。 同様に、$x \in B$ の場合は $y \in A$ です。したがって、すべての辺が $A$ と $B$ の異なる部分に端点を持ちます。

以上により、$G$ は二部グラフであることが示されました。

結論:
$G$ が二部グラフであることと、奇数本の辺を持つ閉路を持たないことは同値です。

10.5 定理1（オイラー閉路の十分かつ必要条件）#

少なくとも2つの頂点を持つ連結多重グラフにおいて、すべての頂点の次数が偶数である場合に限り、オイラー閉路が存在する。

必要条件の証明:
オイラー閉路が存在する連結多重グラフを考えます。この閉路は同じ頂点 $a$ で始まり終わる閉路です。閉路が始点である頂点 $a$ に到達するとき、この頂点の次数は以下のように寄与します：

1. 最初の到達時、次数に1を加算。
2. 最後の離脱時、次数に1を加算。
3. その他の通過時には、到達時と離脱時の2回ずつ加算。

したがって、頂点 $a$ の次数は常に偶数です。同様に、他の頂点も閉路において到達と離脱がセットで起こるため、すべての頂点の次数が偶数である必要があります。

十分条件の証明:
連結多重グラフ $G$ のすべての頂点の次数が偶数であると仮定します。このとき、次のようにオイラー閉路を構成します：

1. 任意の頂点 $a$ を始点として、利用可能な辺を1本ずつ選びながら単純な閉路を作ります。この閉路は有限個の辺しかないため、最終的には $a$ に戻ります。

2. この閉路を取り除いた残りのグラフを $H$ とします。$H$ は以下の性質を持ちます：

   • $H$ のすべての頂点も偶数の次数を持つ。
   • $H$ が連結でない場合、各連結成分について同様の閉路を構成できます。

3. 残りの閉路を元の閉路に統合します。これを全ての辺が使い切られるまで繰り返すと、オイラー閉路が完成します。

結論:
連結多重グラフにおいて、すべての頂点の次数が偶数であれば、オイラー閉路を構成できることが示されました。

10.5 定理2（オイラーパスの十分かつ必要条件）#

連結多重グラフがオイラーパス（ただしオイラー閉路ではない）を持つのは、奇数次数の頂点がちょうど2つ存在する場合に限る。

必要条件の証明:
連結多重グラフ $G$ がオイラーパスを持つと仮定します。このオイラーパスが $a$ から $b$ に至るものとします。

• オイラーパスの最初の辺は $a$ の次数に1を加算します。
• 路が $a$ を通過するたびに、次数に2を加算します。
• 最後の辺は $b$ の次数に1を加算します。

したがって、$a$ と $b$ の次数は奇数になります。それ以外の頂点はすべて通過するたびに次数に2を加算するため、偶数の次数を持ちます。したがって、奇数次数の頂点はちょうど2つである必要があります。

十分条件の証明:
次に、奇数次数の頂点がちょうど2つである連結多重グラフ $G$ を考えます。この頂点を $a$ と $b$ とします。

1. $G$ に仮想的な辺 $\{a, b\}$ を追加して新しいグラフ $G'$ を構成します。
2. $G'$ のすべての頂点の次数が偶数になるため、定理1（オイラー閉路の十分かつ必要条件）により、$G'$ にはオイラー閉路が存在します。
3. $G'$ のこのオイラー閉路から仮想の辺 $\{a, b\}$ を削除すると、元のグラフ $G$ における $a$ から $b$ へのオイラーパスが得られます。

これにより、奇数次数の頂点がちょうど2つ存在する場合、$G$ はオイラーパスを持つことが示されました。

10.5.16#

孤立した頂点を持たない有向多重グラフがオイラー閉路を持つのは、そのグラフが弱連結であり、各頂点の入次数と出次数が等しい場合、かつその場合に限ることを示しなさい。

証明:

1. 必要条件の証明:
   有向多重グラフにオイラー閉路が存在すると仮定します。このオイラー閉路は各頂点を通り、最終的に出発点に戻ります。

   • 弱連結性:
     オイラー閉路が存在するためには、すべての頂点が閉路に含まれる必要があります。このため、グラフは弱連結である必要があります。
   • 入次数と出次数の一致:
     オイラー閉路が各頂点を通過するとき、辺が頂点に「入る」たびに入次数が1加算され、「出る」たびに出次数が1加算されます。最終的に、各頂点の入次数と出次数は同じになります。

2. 十分条件の証明:
   グラフが弱連結であり、各頂点の入次数と出次数が等しいと仮定します。この場合、次の手順でオイラー閉路を構成できます。

   • オイラー閉路の十分条件を示した定理1に基づき、有向グラフにおけるオイラー閉路を構築します。出次数が0になるまで各頂点から出発し、すべての辺を使用する単純な閉路を作成します。
   • すべての辺が使用されるまで、残りの部分グラフに対して同様の手順を適用し、それぞれの閉路を結合して1つのオイラー閉路を完成させます。

結論:
孤立した頂点を持たない有向多重グラフがオイラー閉路を持つのは、グラフが弱連結であり、かつ各頂点の入次数と出次数が等しい場合に限ることが示されました。

10.5.17#

孤立した頂点を持たない有向多重グラフがオイラーパスを持つがオイラー閉路を持たないのは、そのグラフが弱連結であり、すべての頂点の入次数と出次数が等しいが、次の2つの頂点を例外とする場合に限る：

• 1つは出次数が入次数より1大きい頂点（開始頂点）。
• もう1つは入次数が出次数より1大きい頂点（終了頂点）。

証明:

1. 必要条件の証明:
   有向多重グラフがオイラーパスを持つと仮定します。このとき、次の性質が成立します：

   • 入次数と出次数の関係:
     オイラーパスでは、途中で訪れるすべての頂点は、入次数と出次数が等しくなります。なぜなら、訪問時に1本の辺で頂点に「入り」、次の辺で頂点から「出る」ためです。
     ただし、開始頂点では出次数が入次数より1多く、終了頂点では入次数が出次数より1多くなります。これにより、オイラーパスの出発と終了が確定されます。

   • 弱連結性:
     オイラーパスはすべての辺を使用するため、グラフ全体が1つの連結成分に属します。このため、グラフは少なくとも弱連結でなければなりません。

2. 十分条件の証明:
   グラフが弱連結であり、すべての頂点で入次数と出次数が等しいが、以下の2つの例外があると仮定します：

   • 頂点 $u$: 出次数が入次数より1大きい（開始頂点）。
   • 頂点 $v$: 入次数が出次数より1大きい（終了頂点）。

   このとき、次のようにオイラーパスを構築できます：

   • 頂点 $u$ から頂点 $v$ に仮想的な辺を追加した新しいグラフを構成します。この新しいグラフでは、すべての頂点で入次数と出次数が等しくなります。
   • 新しいグラフは弱連結であるため、定理16により、このグラフにはオイラー閉路が存在します。
   • このオイラー閉路から仮想的に追加した辺を削除すると、元のグラフにおける $u$ から $v$ へのオイラーパスが得られます。

結論:
孤立した頂点を持たない有向多重グラフがオイラーパスを持つがオイラー閉路を持たないのは、そのグラフが弱連結であり、すべての頂点で入次数と出次数が等しいが、1つの頂点で出次数が入次数より1大きく、もう1つの頂点で入次数が出次数より1大きい場合に限ることが示されました。

10.6 定理1（ダイクストラのアルゴリズム）#

ダイクストラのアルゴリズムは、連結な単純無向重み付きグラフにおける2つの頂点間の最短経路の長さを見つける。

証明:
数学的帰納法を用いてダイクストラのアルゴリズムが正しいことを示します。各反復における帰納法の仮定は以下の通りです：

1. 帰納法の仮定:
   $k$ 回目の反復において以下が成り立つと仮定する：

   • (i) $S$ に含まれるすべての頂点のラベルは、頂点 $a$ からその頂点への最短経路の長さである。
   • (ii) $S$ に含まれないすべての頂点のラベルは、頂点 $a$ からその頂点への最短経路の長さ（ただし、この経路は $S$ の頂点のみを含む）である。

2. 基底の場合 ($k = 0$):
   初期状態では $S = \emptyset$ であり、すべての頂点のラベルは無限大 ($\infty$) に設定されます。ただし、始点 $a$ のラベルは 0 です。これにより、基底の場合が成り立つことが確認されます。

3. 帰納ステップ ($k \to k+1$):
   帰納法の仮定を用いて、$k+1$ 回目の反復で仮定が成り立つことを示します：

   • 頂点 $v$ を、ラベルが最小の頂点として $S$ に追加します。
   • $v$ のラベルは、$a$ から $v$ への最短経路の長さである必要があります。もしそうでなければ、ラベルが小さい他の頂点が存在することになり矛盾します。
   • $S$ に含まれない頂点については、そのラベルが更新され、次のように計算されます： $$L_{k+1}(u) = \min\{L_k(u), L_k(v) + w(v, u)\},$$ ここで、$w(v, u)$ は頂点 $v$ と $u$ を結ぶ辺の重みです。

4. 結論:
   帰納法により、すべての反復が終了した時点で、各頂点のラベルは頂点 $a$ からその頂点への最短経路の長さとなります。

10.6 定理2（ダイクストラのアルゴリズムの計算量）#

ダイクストラのアルゴリズムは、頂点数 $n$ の連結な単純無向重み付きグラフにおいて、2つの頂点間の最短経路の長さを見つけるために、$O(n^2)$ の操作（加算および比較）を使用する。

証明:

1. 反復回数:
   ダイクストラのアルゴリズムは、グラフの頂点数 $n$ に基づき、最大で $n-1$ 回の反復を行います。各反復で、1つの頂点が集合 $S_k$ に追加されるためです。

2. 各反復での操作数:

   • 最小ラベルを持つ頂点を特定するために、最大で $n-1$ 回の比較が必要です（$S_k$ に含まれない頂点の中から選択するため）。
   • $S_k$ に含まれない各頂点のラベルを更新するためには、加算および比較の操作が必要です。これは各頂点に対して1回行われ、最大 $n-1$ 個の頂点について実行されます。

   したがって、各反復で必要な操作の総数は次のようになります：

   $$2(n-1)$$

   これは最大の加算および比較回数を表します。

3. 全体の計算量:
   最大 $n-1$ 回の反復が行われるため、アルゴリズム全体で必要な操作の合計は次の通りです：

   $$(n-1) \times 2(n-1) = O(n^2)$$

10.7 定理1 （オイラーの公式）#

$G$ を $e$ 本の辺と $v$ 個の頂点を持つ連結平面単純グラフとします。$G$ の平面表現における領域の数を $r$ とすると、以下の式が成り立つ：

$$r = e - v + 2$$

証明:

1. 平面表現の構築:
   $G$ の平面表現を作るために、次の手順で部分グラフの列 $G_1, G_2, \dots, G_e = G$ を構築します：

   • 任意の1つの辺を選択して $G_1$ を作成します。
   • $G_n$ を、既存の部分グラフ $G_{n-1}$ に新しい辺を追加して作成します。このとき、新しい辺は $G_{n-1}$ に既に存在する頂点に接続される必要があります。

   各段階で、領域の数 $r_n$、辺の数 $e_n$、および頂点の数 $v_n$ を記録します。

2. 基底の場合:
   最初の部分グラフ $G_1$ は、1本の辺と2つの頂点を持ち、領域の数は1です。式

   $$r_1 = e_1 - v_1 + 2$$

   は

   $$1 = 1 - 2 + 2$$

   を満たすため、基底の場合が成立します。

3. 帰納法の仮定:
   $G_k$ に対して、以下の式が成り立つと仮定します：

   $$r_k = e_k - v_k + 2$$

4. 帰納ステップ:
   $G_{k+1}$ を $G_k$ に新しい辺 $\{a_{k+1}, b_{k+1}\}$ を追加して得られるグラフとします。この場合、次の2つの状況を考慮します：

   • ケース1: 両端点 $a_{k+1}$ と $b_{k+1}$ が $G_k$ に既に存在している場合：

     • この新しい辺は既存の領域を2つに分割するため、領域の数が1つ増えます（$r_{k+1} = r_k + 1$）。
     • 辺の数は1つ増えます（$e_{k+1} = e_k + 1$）。
     • 頂点の数は変わりません（$v_{k+1} = v_k$）。
     • これにより、次の式が成立します： $$r_{k+1} = e_{k+1} - v_{k+1} + 2$$

   • ケース2: $a_{k+1}$ または $b_{k+1}$ のどちらかが $G_k$ に存在しない場合：

     • 新しい辺の追加により領域の数は変わりません（$r_{k+1} = r_k$）。
     • 辺の数が1つ増え（$e_{k+1} = e_k + 1$）、頂点の数も1つ増えます（$v_{k+1} = v_k + 1$）。
     • これにより、次の式が成立します： $$r_{k+1} = e_{k+1} - v_{k+1} + 2$$

5. 結論:
   帰納法により、すべての $G_n$ において $r_n = e_n - v_n + 2$ が成り立つことが示されました。特に、元のグラフ $G$ においてもこの式が成立します。

10.7 系1#

$G$ を $e$ 本の辺と $v$ 個の頂点を持つ連結平面単純グラフとする。$v \geq 3$ のとき、次が成り立つ：

$$e \leq 3v - 6$$

証明:

1. 領域の次数の性質:
   平面上に描かれた連結平面単純グラフは、平面を $r$ 個の領域に分割します。各領域の次数（その領域の境界に含まれる辺の数）は少なくとも3以上です。これは以下の理由によります：

   • 単純グラフでは、多重辺や自己ループが存在しないため、次数2や1の領域を形成することはありません。
   • 特に、無限領域も少なくとも3以上の次数を持ちます。これは、グラフに少なくとも3つの頂点が含まれているためです。

2. 辺の数と領域の次数の関係:
   グラフのすべての辺は領域の境界に2回現れるため、領域の次数の総和は次のように表されます：

   $$2e = \sum_{\text{faces } R} \deg(R)$$

   また、各領域の次数が3以上であるため：

   $$\sum_{\text{faces } R} \deg(R) \geq 3r$$

   よって次の不等式が得られます：

   $$2e \geq 3r$$

3. オイラーの公式の利用:
   オイラーの公式 $r = e - v + 2$ を用いると、$r$ を $e$ と $v$ によって次のように表せます：

   $$r = e - v + 2$$

   これを $2e \geq 3r$ に代入すると：

   $$\begin{aligned} 2e &\geq 3(e - v + 2) \\ &= 3e - 3v + 6 \end{aligned}$$

   展開して整理すると：

   $$e \leq 3v - 6$$

10.7 系2#

$G$ を連結な平面単純グラフとする。このとき、$G$ には次数が5以下の頂点が存在する。

証明:

1. 場合分け:

   • $G$ の頂点数が1または2の場合、全ての頂点の次数は5以下であるため、命題が成り立ちます。
   • $G$ の頂点数が3以上の場合を考えます。

2. 手がかり:
   コロラリー1より、辺の本数 $e$ と頂点数 $v$ の間には次の不等式が成り立ちます：

   $$e \leq 3v - 6$$

   これに基づき、辺数を次数の和を用いて表すと、ハンドシェーキング定理より次の式が得られます：

   $$2e = \sum_{v \in V} \deg(v)$$

3. 矛盾の導出:
   すべての頂点の次数が6以上であると仮定すると、次数の総和は次のようになります：

   $$\sum_{v \in V} \deg(v) \geq 6v$$

   一方で、コロラリー1の不等式 $e \leq 3v - 6$ を用いると、

   $$2e \leq 6v - 12$$

   これらを比較すると、

   $$6v \leq 6v - 12$$

   となり、明らかに矛盾します。

4. 結論:
   矛盾が生じたことから、すべての頂点が次数6以上であることはあり得ません。したがって、次数が5以下の頂点が少なくとも1つ存在することが示されました。

10.7 系3#

$G$ を $e$ 本の辺と $v$ 個の頂点を持つ連結平面単純グラフとし、$v \geq 3$ であり、長さ3の閉路を持たないとする。このとき次が成り立つ：

$$e \leq 2v - 4$$

証明:

1. 領域の次数に関する条件:
   長さ3の閉路がないため、すべての領域の次数は少なくとも4以上です。これに基づき、領域の次数の合計は次の不等式を満たします：

   $$2e = \sum_{\text{faces } R} \deg(R) \geq 4r$$

   ここで $r$ は領域の数を表します。

2. 領域数 $r$ の式:
   オイラーの公式 $r = e - v + 2$ を用いると、次の式を得ます：

   $$r \leq \frac{e}{2}$$

   したがって、オイラーの公式をこの不等式に代入すると：

   $$e - v + 2 \leq \frac{e}{2}$$

3. 整理:
   上記の不等式を整理すると：

   $$\begin{aligned} 2(e - v + 2) &\leq e \\ 2e - 2v + 4 &\leq e \\ e &\leq 2v - 4 \end{aligned}$$

10.7.17#

$e$ 本の辺と $v$ 個の頂点を持つ連結平面単純グラフがあり、長さ4以下の単純閉路を持たないとします。さらに $v \geq 4$ のとき、次が成り立つ：

$$e \leq \frac{5}{3}v - \frac{10}{3}$$

証明:

1. 領域の次数の性質:
   グラフには長さ4以下の単純閉路が存在しないため、すべての領域の次数は少なくとも5以上です。この条件に基づき、領域の次数の合計は次のように評価できます：

   $$2e = \sum_{\text{faces } R} \deg(R) \geq 5r$$

   ここで、$r$ は領域の数を表します。

2. オイラーの公式の利用:
   オイラーの公式 $r = e - v + 2$ を用いると：

   $$2e \geq 5r$$

   を次のように変形できます：

   $$\begin{aligned} 2e &\geq 5(e - v + 2) \\ &= 5e - 5v + 10 \\ 3e &\leq 5v - 10 \\ e &\leq \frac{5}{3}v - \frac{10}{3} \end{aligned}$$