Симметричный граф: На рисунке схема дорог Н-ского района изображена; 4, 6, 7, 5 · ЕГЭ №1

Подсчитаем степени вершин, то есть число дорог из каждого пункта. На схеме: степень 1 — у Б, Е и К; степень 2 — у Д; степень 3 — у А; степень 4 — у В и Г. В таблице: степень 1 — у П2, П5 и П6; степень 2 — у П7; степень 3 — у П3; степень 4 — у П1 и П4.
А — единственная вершина степени 3, в таблице степень 3 только у П3. Значит, А соответствует П3. Д — единственная вершина степени 2, в таблице степень 2 только у П7. Значит, Д соответствует П7. В — единственная вершина степени 4, не связанная с Д; в таблице с П7 не связан только П4. Значит, В соответствует П4. Г — единственная оставшаяся вершина степени 4 (В уже найдена), в таблице это П1. Значит, Г соответствует П1.
Тогда дорога А–Г — это дорога П1–П3 длиной 7.

$\textbf{Ответ: 7.}$

$\textbf{Решение через Python}$

from itertools import *
t = '2347 1 147 1356 4 4 13'
s = 'В В БЕГА ВГД ВАДК Г ГА'
s = {frozenset(x) for x in s.split()}
for p in permutations('АБВГДЕК'):
    a = t
    for x, y in zip('1234567', p):
        a = a.replace(x,y)
    a = {frozenset(x) for x in a.split()}
    if s == a:
        print('1 2 3 4 5 6 7')
        print(*p)
        break