№ 2. На рисунке — схема двора, севера нет. А, Б, В, Г, Д, Е, Ж, И, К — площадки для развлечения детей, соединённые дорожками. Постройте маршрут прогулки, проходящий через все площадки по одному разу, если: а) в каждой точке должно быть чётное количество дорожек; б) каждая точка, за исключением точки А, имеет только нечётное количество дорожек; в) в каждой точке количество дорожек нечётное, а в соседних площадках количество дорожек соединено по очереди так, что одна площадка с чётным количеством дорожек, другая — с нечётным количеством?

На схеме степени вершин (количество дорожек, подходящих к площадке) таковы: А — 2, Б — 2, В — 2, Г — 4, Д — 4, Е — 4, Ж — 4, И — 4, К — 2. Следовательно, условие а) несовместимо с требованием пройти все площадки по одному разу: при чётной степени каждой вершины граф не может иметь гамильтонов путь, у которого ровно две конечные вершины имеют степень 1 в выбранном маршруте.

Для б) все площадки, кроме А, должны иметь нечётное число дорожек. Это также невозможно: у Б, В и К по две дорожки, а у Г, Д, Е, Ж и И — по четыре, то есть степень каждой из них чётная.

Для в) в условии есть противоречие: сначала сказано, что в каждой точке число дорожек нечётное, а затем требуется чередовать площадки с чётным и нечётным количеством дорожек. Кроме того, по схеме у всех площадок чётные степени.

Поэтому при буквальном понимании условия маршрута для каждого из трёх пунктов нет. Если требуется лишь пройти по одной разной дорожке между последовательными площадками, без ограничения на общее количество дорожек у каждой площадки, возможен маршрут А—Б—В—Г—Д—Е—Ж—И—К: все соседние пары соединены дорожками, и каждая площадка встречается один раз.