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

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

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

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

Задача 5: Докажите, что мост не входит ни в какой цикл.

Задача 6: В Огогондии 2000 городов. Президент издал указ связать их железными дорогами в единую сеть. Каждая ветка связывает два города, не пересекаясь с другими ветками. Докажите, что всего понадобится не менее 1999 веток.

Задача 7: (свойства деревьев). а) В дереве порядка n ровно n – 1 ребро. б) Если в связном графе n – 1 ребро, то это – дерево. в) Каждое ребро дерева – мост.

Задача 8: Из спичек сложили квадрат, разбитый линиями из спичек на 64 квадратных поля со стороной в одну спичку. Какое наименьшее число спичек надо убрать, чтобы с любого поля на любое другое можно было пройти, не перепрыгивая через спички?

Задача 9: (о числе ребер связного графа). В графе порядка n с k компонентами связности – не менее n – k ребер.

Задача 10: Можно ли раскрасить ребра куба в два цвета так, чтобы по ребрам каждого цвета можно было пройти из любой вершины в любую?

Задача 11: В связном графе между любыми двумя вершинами есть маршрут из не более чем трех ребер, а степень каждой вершины не более, чем 4. Докажите, что в графе не более 53-х вершин.

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

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

Задача 14: Докажите, что если в графе порядка n есть не менее n ребер, то в нем есть цикл.

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

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

Задача 17: Каждая грань кубика разбита на 4 квадрата. Некоторые стороны этих квадратов раскрасили в красный цвет – всего 26 сторон. Докажите, что на поверхности кубика найдется замкнутая ломаная из красных отрезков.

Задача 18: В графе с 2n вершинами n² + 1 ребро. Докажите, что в нем есть три вершины, попарно соединенные ребрами.

Задача 19: В компании из k человек (k > 3) каждый узнал по новому анекдоту. За один телефонный разговор двое сообщают друг другу все известные им анекдоты. Пусть n - наименьшее число разговоров, за которые все могут узнать все анекдоты. Докажите, что: а) k – 1 ≤ n ≤ 2k – 3 б) n ≤ 2k – 4 в)* n ≥ 1,5k – 2 г)** n ≥ 2k – 5 д)*** n = 2k – 4.