3. В Изумрудном городе шесть площадей. Каждая площадь соединена улицами ровно с тремя другими площадями. Никакие две улицы в городе не пересекаются. а) Начертите возможный план Изумрудного города. 6) Можно ли устроить экскурсию по всем улицам и площадям Изумрудного города, не проходя ни по одной улице дважды?

a) Возможный план Изумрудного города:

Представим 6 площадей как вершины шестиугольника. Соединим каждую вершину с тремя соседними. У нас получится граф, где каждая вершина связана с тремя другими.

б) Да, можно. Так как каждая площадь связана с тремя другими, каждая вершина графа имеет степень 3. Поскольку все вершины имеют нечетную степень, можно устроить экскурсию по всем улицам и площадям Изумрудного города, не проходя ни по одной улице дважды, начав и закончив экскурсию в разных площадях. Такой путь называется Эйлеровым путем.