植木算の予想（どんなツリーでも頂点の数は辺の数より1つ大きい）を頂点の個数に着目して証明してください

植木算の予想（どんなツリーでも頂点の数は辺の数より1つ大きい）を頂点の個数に着目して証明してください。

ツリーとはどの辺でも1本切ると２つに分かれてしまうグラフのことです。

辺の本数に着目して証明したものが写真です。

No.2 回答者： Tacosan 回答日時： 2016/08/19 00:22

たぶん質問の画像にある証明は #1 と本質的に同じで, そしてそれは「厳密な証明」じゃないんだよね....

で終わるとそれだけなんだけど, これおそらくもとの問題がおかしい. より正確にいうと
「ツリーとはどの辺でも1本切ると２つに分かれてしまうグラフのことです。」
という定義がおかしいために, 結果として「どんなツリーでも頂点の数は辺の数より1つ大きい」が成り立たない「ツリー」ができてしまう, はず.

No.1 回答者： rabbit_cat 回答日時： 2016/08/15 22:49

画像は小さくて読めません。

。

ただ、
＞ツリーとはどの辺でも1本切ると２つに分かれてしまうグラフのことです。
というのをツリーの定義としているのであれば、
当然ですが、辺に注目して証明するのが自然です。
もし、頂点に注目して証明しようとすると、もともと辺に関する性質になっているツリーの定義を、頂点に関する性質に変換しないといけません。

画像が小さくて質問者が示された証明がそうなっているのかどうか分かりませんが、質問文にあるツリーの定義を前提とした上で、一番自然な証明は、
・１本の辺（２頂点）だけで構成させるグラフは、題意を満たす
・辺がn本のグラフで、任意の１本の辺の削除すると、（辺の数がn本未満の）２つの木に分かれてしまいますが、２つのグラフはそれぞれが題意を満たす。
　で、元のグラフは、頂点の数は単純に２つのグラフの頂点の数の和、辺の数は２つのグラフの辺の数の和＋１、なわけで題意を満たす
といった感じの証明で証明でしょう。