G を n 個の頂点 (いずれも孤立していない) と n −1 個の辺 (n ≥ 2) をもつグラフとします。G が次数 1 の頂点を少なくとも 2 つ含むことを示します。
プロパティsummation degree = 2|E|を使用してこの問題を試しました。. この問題は、鳩の巣の原理を使って解決できますか?
1 に答える
1
これを解決するために鳩の穴の原理を使用する賢明な方法は考えられません。次のようにします。
次数の合計 = 2n - 2 = 2|E|
頂点を分離することはできないため、すべての次数が少なくとも 1 でなければならないため、アタッチする「予備の」エッジ エンドが n - 2 あります。n 個の場所に収まる n-2 個の物は、少なくとも 2 個を空にしておく必要があることを意味します (これは鳩の巣の原理に似ていますが、一種の反対です)。したがって、少なくとも 2 つの頂点が次数 1 を持っている必要があります。
ここでこの種の質問をしたほうがよいと思います: https://math.stackexchange.com/
于 2012-05-29T07:43:45.063 に答える