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