Задача 1: Пусть в графе есть незамкнутый эйлеров путь. Тогда степени двух концов этого пути нечетны, а степени всех остальных вершин четны.

Задача 2: Пусть в графе есть эйлеров цикл. Тогда степени всех вершин четны.

Задача 3: На плоскости нарисованы несколько окружностей так, что с любой можно перейти на любую, не сходя с этих окружностей. Докажите, что тогда существует замкнутый путь, проходящий по всем участкам всех окружностей ровно по разу.

Задача 4: Если в графе степени всех вершин четны, то его можно представить в виде объединения циклов так, что каждое ребро входит ровно в один цикл.

Задача 5: Если в связном графе степени всех вершин четны, то в нем есть эйлеров цикл.

Задача 6: Если в связном графе степени ровно двух вершин нечетны, то в нем есть эйлеров путь с концами в нечетных вершинах.

Задача 7: На занятии 20 школьников решили каждый по 2 задачи, причем каждая задача была решена ровно двумя школьниками. Докажите, что можно организовать разбор всех задач так, чтобы каждый школьник рассказал ровно по одной задаче.

Задача 8: Из куска проволоки длиной 12 дециметров требуется спаять каркас куба с ребром в 1 дм. На какое наименьшее число частей придется предварительно разрезать этот кусок?

Задача 9: Город в плане выглядит как квадрат 3 × 3, каждая сторона квартала-квадратика – участок улицы длиной 100 м (включая внешний контур квадрата). Какой наименьший путь придется проделать паровому катку, чтобы заасфальтировать все улицы?

Задача 10: Можно ли сетку, состоящую из границ единичных квадратиков клетчатого квадрата 4 × 4 представить в виде объединения а) восьми ломаных длиной 5; б) пяти ломаных длиной 8?

Задача 11: В Вишкилэнде все авиарейсы беспосадочные, летают туда и обратно, и из любого города (с пересадками) можно долететь в любой другой. Все рейсы поделены между двумя компаниями так, что для любой пары городов все прямые рейсы между ними принадлежат только одной компании, и из любого города рейсами одной компании можно улететь в такое же число городов, в какое и рейсами другой компании. Агенту 007 предписано путешествовать, меняя компанию при каждой пересадке. Докажите, что он может из столицы перелететь в любой город.

Задача 12: На каждой горизонтали и каждой вертикали шахматной доски стоит не менее двух фигур. Всегда ли можно убрать несколько фигур так, чтобы на каждой вертикали и каждой горизонтали стояло ровно по две фигуры?

Задача 13: 100 замов получили взыскания от 100 завов. При этом каждый зав наложил по одному взысканию на 15 замов, а каждый зам получил по одному взысканию от 15 завов. Докажите, что директор может снять часть взысканий так, что у каждого зама останется по одному взысканию, и все взыскания будут наложены разными завами.