logo

握手ジレンマの証明 📂グラフ理論

握手ジレンマの証明

定理 1

任意の有向グラフにおいて、入次数の合計と出次数の合計は等しい。

説明

握手のジレンマは、有向グラフにおける握手の補題と言える。

証明

有向グラフにおいて、出次数の合計はアーク(矢印)の数と同じである。アークは一つの頂点から出て、別の頂点に入るので、出次数と入次数の合計は等しい。


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