Симметричный граф: На рисунке схема дорог N-ского района; 53, 13, 21, 30 · ЕГЭ №1

Подсчитаем степени вершин, то есть число дорог из каждого пункта. На схеме: степень 2 — у G; степень 3 — у A, B, C, D, E и F. В таблице: степень 2 — у П7; степень 3 — у П1, П2, П3, П4, П5 и П6.
G — единственная вершина степени 2, в таблице степень 2 только у П7. Значит, G соответствует П7.
Вершины C и E на схеме неразличимы по уже известным признакам: обе степени 3, обе связаны с G, соседи каждой имеют степени 2, 3 и 3. В таблице так же устроены П2 и П3. Значит, C и E соответствуют П2 и П3, но в каком порядке — по схеме определить нельзя. Для ответа это неважно.
В 1-м варианте дорога E–G — это дорога П3–П7 длиной 3, а дорога G–C — это дорога П2–П7 длиной 39; во 2-м варианте дорога E–G — это дорога П2–П7 длиной 39, а дорога G–C — это дорога П3–П7 длиной 3. Ответ в обоих вариантах одинаковый. Сумма: 3 + 39 = 42.

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

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

from itertools import *
t = '246 157 457 136 236 145 23'
s = 'DBC FBE DAG CE GAF CEB AFD'
s = {frozenset(x) for x in s.split()}
for p in permutations('ABCDEFG'):
    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