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

Найдём сначала связи между населенными пунктами согласно таблице. Пронумеруем вершины графа, соответствующие пунктам, числами от 1 до 6. Из таблицы видно:

• пункт 1 соединён с пунктами 2 и 4; • пункт 2 – с пунктами 1, 4 и 6; • пункт 3 – с пунктами 4 и 5; • пункт 4 – с пунктами 1, 2, 3, 5 и 6; • пункт 5 – с пунктами 3 и 4; • пункт 6 – с пунктами 2 и 4 (ячейка, где записан подозрительный текст, по смыслу должна быть пустой, то есть звёздочка отсутствует).

Таким образом, степени вершин таковы: 1 – 2 ребра, 2 – 3 ребра, 3 – 2 ребра, 4 – 5 ребер (максималь...