グラフが木であるとき、この定義があります。点の個数ｎ 枝の個数ｍ

質問

グラフが木であるとき、この定義があります。点の個数ｎ　　枝の個数ｍ　　そして　ｍ＝ｎ－１
　この詳しい証明過程を教えていただけないでしょうか

回答No.3

Knotopolog · ベストアンサー

証明の前に，少し，おさらいをします．

『木(tree)とは，連結グラフで，サイクルと同型な部分グラフをもたないもの』
を言います．以下，点を頂点といい，枝を辺といいます．

いま，ｎ頂点とは，頂点の数がｎ個の頂点のことで，ｍ辺とは，辺の数がｍ個の辺のこととします．

定理Ａ：グラフＧが連結で，ｎ頂点とｍ辺をもつならば，ｎ≦ｍ＋１ である．

（定理Ａの証明は省略します）

定理Ｂ：Ｇを，ｎ頂点とｍ辺をもつ木とすると，ｎ＝ｍ＋１である．

証明：　辺の個数に関する帰納法で証明します．Ｇが辺をもたないならば，定理Ｂは，このＧについては，正しい．
ｍ辺より少ない辺をもつ木については，定理Ｂが正しいと仮定する．
いま，Ｇの最長の道を選び，その端頂点をａとｂとする．
頂点ａは，次数１です．もし，そうでないとすると，この道は，もっと長くすることが出来るか，
または，Ｇにサイクルが存在してしまうことになるからです．
ここで，「頂点ａ」と「頂点ａと接続する辺」を取り除く．こうして得られたグラフをＨとする．
Ｈは，まだ依然として木であり，ｎ－１頂点と，ｍ－１辺をもつ．帰納法の仮定から，
ｎ－１＝(ｍ－１)＋１です．これにより，ｎ＝ｍ＋１であり，
定理Ｂは，Ｇについても正しい．■

ちょっと，すっきりしない証明かも知れませんので，以下に木に関する別の定理を書いておきます．

定理Ｃ：グラフＧが連結で，ｎ＝ｍ＋１ならば，Ｇは木である．

証明：定理Ｃが正しくないと仮定すると，連結なグラフＧで，ｎ＝ｍ＋１であるが，
木でないグラフが存在することになる．いま，Ｇは木でないのだから，Ｇはサイクルを含む．
このサイクル上の１辺を取り除くことにより，連結でｎ頂点とｍ－１辺をもつグラフＨを得る．
定理Ａにより，ｎ≦(ｍ－１)＋１＝ｍ となるが，ｎ＝ｍ＋１と仮定したのだから，
これは矛盾である．よって，Ｇは木である．■

（余談）直感的に，感覚的に，木のｎ＝ｍ＋１を理解するには，
頂点と辺（点と枝）を一対にしたもの（ ―――● ）を木から，何度も取り除いてゆく．
頂点と辺の数は有限なので，最後に頂点（●）だけが１個の残ります．
これが，直感的な証明です．

（一応，見直したのですが，どこかに誤記や間違いがあるかも知れません．
今は，気が付きませんが，間違えていたら，ごめんなさい）

お礼

ありがとうございます～

回答No.2

Tacosan

「定義」は証明するものじゃないね.
で, 「木」はどのように定義されているのですか?

回答No.1

nag0720

帰納法で証明したら。

枝が１本のときと、木に枝が１本増えたときを示す。