Задача 1: Сколько всего ребер в графе ладьи?

Задача 2: Каково наибольшее возможное число ребер в графе с n вершинами?

Задача 3: Какова наибольшая степень вершины в графах а) коня; б) ферзя?

Задача 4: Сколько всего ребер в графе короля?

Задача 5: Сумма степеней всех вершин равна удвоенному числу ребер.

Задача 6: (лемма о рукопожатиях). В конечном графе число вершин нечетной степени – четно.

Задача 7: Верна ли лемма о рукопожатиях для бесконечного графа?

Задача 8: Можно ли расположить на столе 7 монет так, чтобы каждая касалась ровно трех других?

Задача 9: При каких n граф коня на доске n × n не связный?

Задача 10: В стране Оз 15 городов, каждый из которых соединен авиалиниями не менее, чем с 7 другими. Докажите, что из любого города можно самолетом добраться до любого другого (возможно, с пересадками).

Задача 11: На сколько компонент связности распадается граф слона?

Задача 12: Турист приехал на вокзал и отправился гулять по улицам Москвы. Докажите, что он в любой момент может вернуться на вокзал, проходя только по тем участкам улиц, по которым он уже проходил нечетное число раз.

Задача 13: В Зазеркалье из Котельнича выходит 2001 дорога, из деревни Вишкиль – одна, а из всех остальных городов по 1000 дорог. Докажите, что из Котельнича по дорогам можно попасть в деревню Вишкиль.

Задача 14: В связном графе степень каждой вершины четна. Одно ребро удалили (оставив, однако, вершины на его концах). Докажите, что граф остался связным.

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

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

Задача 17: Можно ли подобрать компанию, где у каждого ее члена было бы пять друзей, а у любых двух – ровно два общих друга?

Задача 18: Докажите, что из каждого связного графа можно удалить одну вершину и все выходящие из нее ребра так, что останется связный граф.