📂グラフ理論

ケーニヒの定理の証明

定理 ¹

$G$ を 局所的に有限な 連結グラフとする。すると、すべての $v \in V(G)$ に対して $v$ を始点とする片方向無限パスが存在する。

証明

$G$ は連結グラフであるため、$v$ ではないすべての $z \in V(G)$ に対して、$v$ から $z$ へのパスが無限に存在する。そして、$G$ が局所的に有限であるため、これら無限に多いパスの中で、無限に多いものは同じエッジで始まらなければならない。このエッジを $vv_{1}$ とする。同じ方法で、新しいエッジ $v_{1}v_{2}$ を選ぶことができる。このようにして、次の片方向無限パスが得られる。 $$ v \to v_{1} \to v_{2} \to \cdots $$

■