全域木がマトロイドの基になるやつ

こんにちは。理情に入ってからフラフラと生きてきましたがやっとこさ希望研究室を決めたのでグラフ理論についてヒーコラ言いながら勉強しているぶるーまんです。

マトロイドの各種公理系が色々あり全域木は基の性質を満たしていることは有名なやつだと思いますがその証明を考えていたときに一次従属でえいやっとするやつを思い浮かんだのでどっかしら100％既出だとは思いますが書いてみます。こういう感じで色々勉強したこと書けたら良いね。とりあえず図は気分が載ったときに付け加えたいと思います。

既存の証明としては基本閉路/カットを使ったけんちょんさんの↓

drken1215.hatenablog.comが分かりやすかったので貼っておきます。

定義

マトロイドの基とは有限集合E上の集合族 $\mathcal{B}$ で以下の2条件を満たすもの

(i) $\mathcal{B}$ の要素はお互いの真部分集合ではない。

(ii) $B_1,B_2\in \mathcal{B}$ で

$\forall e\in B_1\setminus B_2 ,\exists f \in B_2\setminus B_1 :(B_1 \setminus \{e\})\cup \{f\} \in \mathcal{B}$

以下グラフGは連結とします（非連結の場合はまあそれぞれでやればいいでしょ多分）

証明

(i)はそう。(ii)について背理法を使う。つまり $T_1,T_2$ をグラフ $G$ の全域木として

$\exists e \in T_1\setminus T_2, \forall f \in T_2\setminus T_1$

$(T_1\setminus \{e\})\cup \{f\}$ は全域木ではない

ということを仮定します。

面倒なので以降 $T'_1 = T_1\setminus\{e\}$ と書きます。

全域木の辺数は全て $|G|-1$ なので $|T'_1| = |T_2| - 1$

この $\forall f\in T_2\setminus T'_1$ に対して $T'_1\cup \{f\}$ は全域木ではないので閉路Cを含む。Cはもともと $T_1$ が木だった事からせいぜい１つのはずなので一意になる。またこのCが $T_2$ の元だけからなると $T_2$ が木だったことに矛盾するので $T'_1 \setminus T_2$ の元を少なくとも１つ含むはず。それを $C_f = C \cap T'_1\setminus T_2$ と表記するとして各 $f\in T_2\setminus T'_1$ に対し非空の $C_f \subset T'_1 \setminus T_2$ が定まっている。

この時fの候補は $k$ 個で $C_f$ に含まれる元の個数は $k-1$ 個以下なので対称和により $T'_1 \setminus T_2$ を $F_2$ のベクトル空間とみなすと $\{C_f | f\in T_2\setminus T'_1\}$ は $k-1$ 次元ベクトル空間上での $k$ 個非零ベクトルを考えていることになるので $\{f_1, f_2...f_n\}$ が存在して $f_1 + ... + f_n = 0$ となる。

閉路の対称和は0個以上の素な閉路の和となるので今とったn個の閉路の対称和は0個以上の閉路の和であり $f_1 + ... f_n = 0$ より $T'_1\setminus T_2$ の要素を含まない。また $f_i$ は $C_f$ にのみ含まれるので相殺されることはなくよって出来上がった閉路の和は空ではない。つまりT_2内に１つ以上の閉路を含むことになるがこれは矛盾。