logo

ケーニヒの定理の証明 📂グラフ理論

ケーニヒの定理の証明

定理 1

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

証明

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


  1. Wilson. (1970). Introduction to Graph Theory: p78. ↩︎