Никита составил схему автобусного сообщения между деревнями

[gevaraweb]

Никита составил схему автобусного сообщения между деревнями.
Илья составил таблицу автобусных сообщений между населенными пунктами.
Илья пронумеровал деревни, а наличие автобусного сообщения обозначил звездочкой.

Сравнив схему и таблицу, мальчики обнаружили, что на схеме есть маршрут, который не указан в таблице. Определите, какой это маршрут.

В таблице и на графе пункты обозначены по-разному.
В ответе запишите два числа, соответствующие этим населенным пунктам, в порядке возрастания без пробелов и знаков препинания.





Если пристально смотреть на таблицу, то видно, что не хватает Вершины с 4 путями для Пункта Карелы.

Добавляем вершину, проверяя, чтобы при этом не образовалось две вершины с 4 путями.
Но возможных вариантов слишком много. Как их отсеять?

[svv]

Ясно, что маршруты Карелы—Толстовка и Карелы—Боловитино не могли быть пропущены в таблице.
Зацепка: если убрать ребро Карелы—Антоновка, возникнет уникальная особенность — две смежные вершины степени 2 (Боловитино и Антоновка). Их легко найти и в таблице. В графе, полученном из исходного удалением ребра Карелы—Ухтынск, вершин с таким свойством нет.

[svv]

svv в сообщении #1640074 писал(а):

Боловитино

Извиняюсь, Болотовино.

[gevaraweb]

gevaraweb в сообщении #1640107 писал(а):

Зацепка: если убрать ребро Карелы—Антоновка, возникнет уникальная особенность — две смежные вершины степени 2

Хм, действительно ).
Посчитал степени вершин в таблице, степень 2 имеют вершины №1, №4, №5.
Смежными являются №1 и №5.
Итак, Болотовино и Антоновка - это (№1, №5) или (№5, №1). Дальше опять тупик
Новое ребро должно добавить вершину степени 4.
Пока вершины степени 3 это №2, №3, №6, №7.
Соединяем одну из (№1, №5) с одной из (№2, №3, №6, №7). Опять много вариантов.

А, Толстовка, получается, имеет номер №4.
А, аналогично: если убрать ребро Карелы—Антоновка, возникнет еще уникальная особенность —
ровно одна из вершины степени 3 имеет две смежные вершины степени 2.
Это вершина №6. Итак, Карелы имеет номер №6.

Далее уже раскручивается...
Толстовка смежна с Карелы и Алексеевка.
При этом №4 смежна с №6 и №2.

Итак, Алексеевка имеет номер №2.

Далее Ухтынск и Клименки - им остается пара №3 и №7, или наоборот.
Карелы смежна с Ухтынск, а в таблице с №7, поэтому Ухтынск имеет №7.
Соответственно, Клименки имеет №3.

Ну теперь и Антоновка - это №5. Болотовино это №1.
svv, благодарю.
Тяжелая задача (имеется в виду, соседний вариант гораздо очевиднее).