74. Какое максимальное число кёнигсбергских мостов можно пройти по одному разу и вернуться в исходную точку? А если не требовать возвращения в исходную точку?

В графе кёнигсбергских мостов четыре вершины имеют нечётные степени: три вершины степени 3 и одна степени 5.

Чтобы пройти по рёбрам без повторений и вернуться в исходную точку, в выбранном наборе рёбер степень каждой вершины должна быть чётной. В этом графе можно составить замкнутый маршрут по пяти мостам, но нельзя по шести: при удалении двух мостов останется не более пяти, если требуется получить связный подграф с чётными степенями.

Если возвращаться не нужно, допустим маршрут, у которого ровно две вершины нечётной степени. Можно пройти по шести мостам без повторений; пройти так все семь невозможно, поскольку в исходном графе четыре вершины нечётной степени.

Ответ: с возвращением — 5 мостов; без возвращения — 6 мостов.