Симметричный граф: На рисунке схема дорог Н-ского района; 9, 17, 15, 10 · ЕГЭ №1

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

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

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

from itertools import *
t = '57 6 6 67 17 2347 1456'
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