組合せとグラフの理論（塩田）第3回 (3) 連結性
連結性
Def.5 グラフが連結である、とは、２つの部分グラフの和にはなっていないこと。
和になっていると、全体としてはつながっていないよね、という意味です。
$C_3 \cup C_4$
Th.6 任意の有限無向グラフ $G$ は、連結な部分グラフたち ( $G$ の連結成分、と呼ぶ ) の和になる。
証明 $G$ が連結ならば $G$ の連結成分は $G$ ひとつ。$G$ が連結でなければ $G=G_1 \cup G_2$ と書け、
帰納法の仮定より $G_1$, $G_2$ は連結な部分グラフたちの和になるので。(証明終)