二部グラフ \(G=(V, U, E)\) が森であるならぱ、
\(|E| \leq|V|+|U|-1\)
という不等式が成り立つ理由を説明 します。ここで、森とは閉路を含まないグラフを指します。
まず、基本的なグラフ理論の概念について確認しましょう。
グラフ理論の確認
1. 木と森の定義:
・木: 閉路を持たない連結なグラフ。
・森: 閉路を持たないグラフ（つまり、複数の木の集合）。
2. 二部グラフ:
・グラフ \(G=(V, U, E)\) が二部グラフである場合、頂点集合 \(V\) と \(U\) は互いに独立であり、エッジ \(E\) は \(V\) の頂点と \(U\) の頂点の間にのみ存在します。
3. エッジの数に関する基本性質:
・木には \(n\) 個の頂点と \(n-1\) 個のエッジがある。
・森には \(k\) 個の連結成分があり、それぞれの成分は木であり、全体で \(n\) 個の頂点を持つ場合、エッジの 数は \(n-k\) 個です。
これらの性質を用いて、二部グラフ \( G=(V, U, E)\) が森である場合のエッジの数に関する不等式を証明します
証明
頂点の数:
・グラフ \(G\) の頂点の総数は \(|V|+|U|\) です。
連結成分の数:
・グラフ \(G\) に \(k\) 個の連結成分があるとします。各連結成分は木であるため、成分 \(i\) の頂点数を \(n_i 、\) 、エッジ数を \(n_i-1\) と表せます。
全体のエッジ数:
・グラフ \(G\) のエッジの総数は、各成分のエッジ数の和です。すなわち、
$$
|E|=\sum_{i=1}^k\left(n_i-1\right)=\left(\sum_{i=1}^k n_i\right)-k
$$
ここで、全体の頂点数は \(\sum_{i=1}^k n_i=|V|+|U|\) であるため、
$$
|E|=(|V|+|U|)-k
$$
連結成分の数の最小値:
・森の連結成分の数 \(k\) は少なくとも 1であり、最も多くても \(|V|+|U|\) です。しかし、最大でも \(|V|+\) \(|U|-1\) という不等式を満たすためには \(k\) が少なくとも 1 であることが重要です。
以上より次の不等式が成り立ちます。
$$
|E| \leq|V|+|U|-1
$$
これは、森に含まれるエッジの数がその頂点から連結成分を引いたものであり、連結成分の数が少なくとも１であるためです。
この不等式により、非ゼロ成分が\(|V|+|U|-1\)より多い場合、閉路が存在することが示されます。したがって、森であるならばこの不等式が成り立ちます。
補足：森と木の性質
木の基本性質
木の基本性質の1つとして、頂点の数を \(n\) とすると、エッジの数は \(n-1\) であるというものがあります。これを証明し ます。
証明
証明は帰納法を用いて行います
基底（ \(n=1\) の場合）
1つの頂点を持つ木にはエッジが1つもありません。したがって、頂点が1つの木についてはエッジの数は \(1-1=0\) で あり、命題は成り立ちます。
帰納ステップ
任意の \(n\) について、頂点が \(n\) の木にエッジが \(n-1\) 本あると仮定します。この仮定のもとで、頂点が \(n+1\) の木 について命題が成り立つことを示します。
1. 頂点が \(n\) の木 \(T\) を考えます。 \(T\) のエッジの数は \(n-1\) 本です。
2. \(T\) に新しい頂点 \(v\) を追加し、その丁頁点を既存の木の任意の頂点 \(u\) に接続します。この操作により、新しいエッジが1本追加されます。
3. この操作後、木は依然として連結であり、閉路を持たないので、木の性質を保ちます。
4. 追加された新しい頂点 \(v\) により、頂点の総数は \(n+1\) となり、エッジの総数は \((n-1)+1=n\) となりま す。
このように、頂点が \(n+1\) の木についてエッジの数は \((n+1)-1=n\) であることが示されました。
したがって、帰納法により、頂点が \(n\) の木についてエツジの数は常に \(n-1\) であることが証明されました。
森の基本的性質
森には \(k\) 個の連結成分（それぞれが木）があり、頂点の総数を \(n\) とすると、エッジの総数は \(n-k\) であるという 性質があります。
証明
これを証明するために、森の性質を考えます。
1. 森には \(k\) 個の連結成分があり、それぞれが木です。各連結成分 \(i\) の頂点数を \(n_i\) とします。
2. 木の性質により、各連結成分 \(i\) のエッジ数は \(n_i-1\) です。
3. 森のエッジの総数は、各連結成分のエッジ数の総和です。したがって、
$$
|E|=\sum_{i=1}^k\left(n_i-1\right)
$$
4. ここで、頂点の総数 \(n\) は \(\sum_{i=1}^k n_i\) です。よって、
$$
|E|=\left(\sum_{i=1}^k n_i\right)-k=n-k
$$
このようにして、森のエッジの総数が \(n-k\) であることが証明されました。