ケーニヒの定理の証明
定理 1
を 局所的に有限な 連結グラフとする。すると、すべての に対して を始点とする片方向無限パスが存在する。
証明
は連結グラフであるため、 ではないすべての に対して、 から へのパスが無限に存在する。そして、 が局所的に有限であるため、これら無限に多いパスの中で、無限に多いものは同じエッジで始まらなければならない。このエッジを とする。同じ方法で、新しいエッジ を選ぶことができる。このようにして、次の片方向無限パスが得られる。
■
Wilson. (1970). Introduction to Graph Theory: p78. ↩︎