В дереве на 13 вершинах есть ровно две вершины степени 6. Следует ли из этого, что в этом дереве есть вершина степени 2?

Пусть вершины $ v_1 $ и $ v_2 $ имеют степень 6.$ \sum_{i=1}^{n}{deg(v_i)} = 24 $, т.к. в дереве на 13 вершинах 12 ребер.
Тогда $ \sum_{i=3}^{n}{deg(v_i)} = 12 $. Cреди 11 вершин должна быть хотя бы 1 вершина четной степени, потому
что иначе сумма 11 нечетных чисел– нечетное число. Пусть это вершина $ v_3 $. Предположим, что
$ deg(v_3) \neq 2 $ ⇒ degv3 ≥ 4. Но тогда $ \sum_{i=3}^{n}{deg(v_i)} $ ≥ 4 + 10 · 1 = 14 > 12 ⇒ ∃vi: $ deg(v_3) $ = 2


info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp