グラフ理論（木について）の証明

2点以上の点からなる木は、2部グラフであることを数学的帰納法を用いて証明するには、どのようにしたらよいのでしょうか？
※使っても良い事実として、「2点以上の点からなる木では葉が存在する」というものがあります。
点の個数が2のときは明らかであることは分かるのですが、その後どのようにしたらよいのかが分かりません。
（もし、点の個数を使うときはn，辺の個数はeを用いて教えてください）
よろしくお願いします。

No.2 ベストアンサー 回答者： Tacosan 回答日時： 2008/07/04 01:26

まあ, こんなの別に帰納法を使うまでもなく

・適当な頂点を根とする根付き木として
・根からの深さが偶数の頂点と奇数の頂点に分ける
だけで終わりなんですけどね.

この回答へのお礼

お礼が遅くなって申し訳ありません。
こちらの回答と、友達の考えを合わせて、解くことができました。

ありがとうございます。
そして、これかたもよろしくお願いします。

お礼日時：2008/07/28 17:45

No.1 回答者： Tacosan 回答日時： 2008/07/03 23:38

木が閉路を持たないことを使うのが簡単かなぁ.

例えば, 「木が葉を持つ」ことは使っていいということなので, 木T が与えられたときに, その 1つの葉 v を取り除いてみてください. そうすると, 1つ頂点の少ない木が得られますね.

この回答への補足

申し訳ないのですが、できればもう少し具体的に教えていただけませんでしょうか？

補足日時：2008/07/09 20:13