グラフ理論木を記述する

Question

木に次数8の1000の頂点と次数5の頂点40、おそらく他の頂点があるとします。そのような木には4000枚以下の葉がありますか？もしそうなら、私はそのような木をどのように記述することができますか？そうでなければ、そのような木は存在しないと主張する方法はありますか？

Answer 1

いいえnが頂点の総数である場合、ツリーはn-1個の辺を持ち、頂点の次数の和は辺の数の2倍です。したがって2n-2です。

次数8のノードの数をrとすると、次数1のノード（葉）と残りの1のノード（したがって、それらの次数が少なくとも2である）とします。次に、n = r + s + tおよび2n-2 = 2r + 2s + 2t-2> = 8r + s + 2t（度の合計に対する下限）。したがって、s-2> = 6rとなる。 r = 1000の場合、6000以上の葉があります。