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

質問

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

回答No.2

Tacosan

まあ, こんなの別に帰納法を使うまでもなく
・適当な頂点を根とする根付き木として
・根からの深さが偶数の頂点と奇数の頂点に分ける
だけで終わりなんですけどね.

お礼

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

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

回答No.1

Tacosan

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

補足

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