Найти в графе G число вершин степени 1...

[Fliffy]

Доброго времени суток! Интересует решение следующей задачи:
В связном графе (без петель и кратных ребер) G, в котором ровно один цикл, степень любой вершины равна либо 1, либо 2, либо 3, причем вершин степени 1 равно 2022. Найти в графе G число вершин степени 3.
Мои примитивные рассуждения были следующими:
Рассмотреть такой же по условиям граф, но с меньшим числом вершин, например количество вершин степени 1 равно 4. Например такой:

Тогда число вершин со степенью 1 (3,5,7,9) равно 4 и количество вершин со степенью 3 (2,4,6,8) равно 4. Здесь ровно один цикл: 1->2->4->6->8->1. Но возникает вопрос, можно ли считать циклом 1->2->3->2->1 или 1->2->4->5->4->2->1? Про то, что цикл простой в условии ничего не сказано.
Если такой же по условиям граф, но количество вершин степени 1 равно, например, 6:

Здесь опять же получается, что число вершин со степенью 3 равно числу вершин со степенью один, то есть 6.
В итоге ответ на исходную задачу получается: число вершин со степенью 3 равно 2022. Но меня терзают смутные сомнения...

[tolstopuz]

Не рассмотрен случай, когда к вершине цикла прикреплена не одна вершина степени 1, а целое поддерево.

[Fliffy]

Например такой:

Получается тоже самое, что число вершин со степенью 1 совпадает с числом вершин со степенью 3. Можно ли это как-то по другому доказать?

[mihaild]

Давайте возьмем наш граф за вершину степени 1 и оторвем её. Она была прикреплена к вершине степени 2 или 3 (иначе граф был несвязным). Что в каждом из этих случаев происходит с числом вершин степени 1 и 3?

[Fliffy]

Число вершин степени 1 и 3 уменьшается на 1)

[mihaild]

Нет. Например добавьте к графу на последней картинке вершину 10, соединенную с 4. Что будет при её удалении?

[Fliffy]

Тогда ничего не поменяется. Но если, например, удалить вершину 4 из графа на последнем рисунке, то количество вершин со степенью 1 и 3 будет равно трем.

[mihaild]

Правильно. Так какой список вариантов, что может произойти при удалении из графа вершины степени 1?
И пусть в графе нет вершин степени 1. Сколько в нем вершин степени 3?

[Fliffy]

Есть два варианта:
1) Ничего не меняется
2) Количество вершин со степенью 1 и 3 уменьшается на 1
Если в графе не останется вершин степени 1, то и вершин степени 3 не будет.

[mihaild]

Из этого уже доказательство получается в одну строчку.

[Fliffy]

Понял, спасибо:)