Пусть G — граф с n вершинами, ни одна из которых не является изолированной, и n−1 ребрами, где n ≥ 2. Покажите, что G содержит по крайней мере две вершины степени 1.
Я пробовал эту проблему, используя свойство summation degree = 2|E| . Можно ли решить эту проблему, используя принцип голубятни?
Я не могу придумать разумного способа использовать принцип голубятни для решения этой проблемы, я бы сделал это так:
Сумма степеней = 2n - 2 = 2|E|
Поскольку никакие вершины не могут быть изолированы, все они должны иметь степень не менее 1, поэтому необходимо присоединить n - 2 «запасных» конца ребра. n-2 вещи, чтобы поместиться в n местах, означают, что по крайней мере 2 должны быть оставлены пустыми (это похоже на принцип ящика для ящиков, но немного противоположно), поэтому по крайней мере 2 вершины должны иметь степень 1.
Я думаю, вам лучше задать такой вопрос здесь: https://math.stackexchange.com/
