Задача 1: На первом этаже замка 13 комнат. Может ли каждая из них граничить с 1, 3 или 7 другими комнатами?

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

Задача 3: Во дворе живут 4 песика: Бобик, Робик, Тобик и Толстолобик. Каждому из них случалось драться с кем-нибудь из остальных, причем у Бобика, Робика и Тобика число тех, с кем они дрались – разное. Со сколькими собаками двора дрался Толстолобик?

Задача 4: Степень каждой вершины связного графа – не менее 100. Одно ребро выкинули. Может ли получиться несвязный граф?

Задача 5: Докажите, что на любой географической карте с 2000 странами найдутся по крайней мере две страны с одинаковым числом соседей.

а) Является ли граф слона связным?

б) Сколько компонент связности имеет этот граф?

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

Задача 7: На плоскости нарисованы вершины графа, пронумерованные числами от 2 до 30. При этом две вершины с номерами a и b соединены ребром только в том случае, если одно из чисел a или b делится на другое. Сколько компонент связности имеет этот граф?

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

Задача 9: Петя заметил, что у всех его 25 одноклассников различное число друзей в этом классе. Сколько может быть друзей у Пети? (Укажите все решения)

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

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

Задача 12: На дискотеке каждый юноша знаком не менее чем с 5-ю девушками, а каждая девушка – не более чем с 5-ю юношами. Докажите, что каждый юноша может пригласить знакомую девушку на танец (все пары танцуют одновременно).

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