Задача 1: Имеется 30 человек, некоторые из них знакомы. Доказать, что число человек, имеющих нечетное число знакомых, четно.

Задача 2: В кружке у любого члена имеется один друг и один враг. Доказать, что

a) число членов четно.

b) кружок можно разделить на 2 нейтральных кружка.

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

Задача 4: В некоторой стране из столицы выходит 89 дорог, из города Дальний – 1 дорога, из остальных 1988 городов – по 20 дорог. Доказать, что из столицы можно проехать в Дальний.

Решение: Если бы столица и город Дальнийй не были связаны, то в компоненте связности столицы было бы нечётное число (один) городов, из которых выходит нечётное число дорог.

Задача 5: 20 школьников решали 20 задач. Каждый решил ровно две задачи, и каждую задачу решили ровно двое. Доказать, что можно устроить разбор задач так, чтобы каждый рассказал одну решенную им задачу.

Решение: Если в графе степень любой вершины равна двум, то он разбивается на циклы.

Задача 6: Из полного 100-вершинного графа выкинули 98 ребер. Доказать, что он остался связным.

Задача 7: На клетчатом листе закрасили 25 клеток. Может ли каждая из них иметь нечетное число закрашенных соседей?

Задача 8: Могут ли степени вершин в графе быть равны:

a) 8, 6, 5, 4, 4, 3, 2, 2.

b) 7, 7, 6, 5, 4, 2, 2, 1.

c) 6, 6, 6, 5, 5, 3, 2, 2.

Решение: Нет. а) В графе из восьми вершин степень 8 встретиться не может

b) Если есть две вершины, связанные со всеми, то то степень любой другой вешины не менее двух.

c) Сумма степеней вершин должна быть чётной.

Задача 9: В графе каждая вершина – синяя или зеленая. При этом каждая синяя вершина связана с синими и зелеными, а каждая зеленая – с синими и зелеными. Каких вершин больше – синих или зеленых?

Решение: Зелёных вершин больше. Подсказка: одноцветные рёбра можно не учитывать.

Задача 10: В графе 100 вершин, причем степень любой из них не меньше 50. Доказать, что граф связен.

Задача 11: Есть 20 карточек, у каждой из которых на двух сторонах написано по числу. При этом все числа от 1 до 20 написаны по два раза. Доказать, что карточки можно разложить так, чтобы все числа сверху были различны.

Задача 12: У царя Гвидона было 3 сына, из его потомков 100 имело по 3 сына, а остальные умерли бездетными. Сколько потомков у Гвидона?

Решение: 303 потомка

Задача 13: В графе из любой вершины выходит по 3 ребра. Может ли в нем быть 1990 ребер?

Задача 14: Доказать, что число штатов США с нечетным числом соседей четно.

Задача 15: В классе больше 32, но меньше 40 человек. Любой мальчик дружит с тремя девочками, а любая девочка – с пятью мальчиками. Сколько человек в классе?

Задача 16: Доказать, что из связного графа можно выкинуть вершину, оставив его связным.

Задача 17: В связном графе любая вершина имеет степень, равную 100. Доказать, что от выкидывания одного ребра связность не нарушится.

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

Решение: Пусть a и b – две вершины, A – множество из 40 вершин, в которые ведут рёбра из a, B – множество из 40 вершин, из которых идут рёбра в b, C – множество из оставшихся 19 вершин. Предположим, что из a нельзя пройти в b по трём рёбрам. Тогда все рёбра, выходящие из A, идут в A или в C. Этих рёбер по условию всего 40 • 40. Но рёбер внутри A не больше чем , а рёбер из A в C не больше чем 40 • 19, что в сумме даёт меньше, чем 40 • 40. Противоречие.

Задача 19: Грани некоторого многогранника раскрашены в два цвета так, что соседние грани имеют разные цвета. Известно, что все грани, кроме одной, имеют число ребер, делящееся на 3. Доказать, что и эта одна грань имеет делящееся на 3 число ребер.

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

Решение: Это город, из которого выходит наибольшее число дорог.

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

Решение: Доказывайте это по индукции.

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

Задача 23: В графе 20 вершин, степень любой не меньше 10. Доказать, что в нем есть гамильтонов путь.

Решение: Выберем самый длинный путь, в котором вершины не повторяются. Предположим, что он содержит не все вершины. Тогда в нём есть две соседние вершины, одна из которых соединена с концом пути, а другая – с вершиной вне пути. Имея такие вершины, нетрудно удлинить путь.

Задача 24: Можно ли начертить, не отрывая карандаша от бумаги (одним росчерком)

a) Квадрат с диагоналями ?

b) Шестиугольник со всеми диагоналями ?

Задача 25: Существует ли ломаная, пересекающая все ребра картинки по одному разу?

Задача 26: Доказать, что связное множество, состоящее из нескольких окружностей, можно начертить одним росчерком.

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

b) Доказать обратное: если в связном графе вершин с нечетной степенью не больше двух, то в нем есть эйлеров путь.

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

Задача 29: a) Из какого минимального числа кусков проволоки можно спаять каркас куба?

b) Какой максимальной длины кусок проволоки можно вырезать из этого каркаса?

Задача 30: Дерево – это связный граф без циклов. Доказать, что

a) Из связного графа можно выкинуть несколько ребер так, чтобы осталось дерево.

b) В дереве с n вершинами ровно n – 1 ребер.

c) В дереве не меньше двух висячих вершин.

d) В связном графа из n – 1 вершин не меньше n – 1 ребер.

e) Если в связном графа n вершин и n – 1 ребер, то он – дерево.

Задача 31: Есть волейбольная сетка 5 × 10. Какое максимальное число веревок, ее составляющих, можно разрезать так, чтобы она не распалась?

Решение: Подсказка: после разрезаний останется дерево.

Задача 32: Доказать, что из любых шести человек можно выбрать трехпопарно знакомых или трех попарно незнакомых.

Задача 33: Ребра полного 6-вершинного графа раскрашены в два цвета. Доказать, что найдется одноцветный треугольник.

Задача 34: Ребра полного 17-вершинного графа раскрашены в три цвета. Доказать, что найдется одноцветный треугольник.

Решение: Выберем одну вершину. Из неё выходит 6 одноцветных рёбер (принцип Дирихле). Примените задачу 33 к вершинам, в которые идут эти рёбра.

Задача 35: Ребра 18-вершинного полного графа раскрашены в 3 цвета. Доказать, что есть полный одноцветный подграф из вершин.

Решение: Докажите сначала такое утверждение: в полном 9-вершинном графе, раскрашенном в два цвета, найдётся или треугольник первого цвета, или полный четырёхвершинный подграф второго цвета. Далльще действуйте как в задаче 34.

Задача 36: Какое наибольшее число ребер может быть в 30-вершинном графе, в котором нет полного подграфа из четырех вершин ?

Решение: Ответ: 225. Подсказка: в графе из n вершин без треугольников есть вершина со степенью. не больше

Задача 37: Ребра полного 18-вершинного графа раскрашены в 2 цвета.Доказать, что найдется полный одноцветный подграф из четырех вершин.

Решение: Доказывайте это по индукции

Задача 38: Доказать теорему Эйлера для связного непустого графа, нарисованного на плоскости:

где В – число вершин, Р – число ребер, Г – число областей, на которые граф делит плоскость (включая внешнюю).

Задача 39: Доказать, что в плоском графе РГ, если Р ≥ 2 (Р – число ребер, Г – число областей).

Задача 40: Доказать, что полный 5-вершинный граф нельзя нарисовать на плоскости.

Задача 41: В графе степень любой вершины не меньше шести. Доказать, что его нельзя нарисовать на плоскости.

Решение: Подсказка: в таком графе любая область имеет не меньше четырёх закрашенных рёбер.

Задача 42: Доказать, что в двудольном плоском графе Р ≥ 2Г, если Р ≥ 2. ( Р – число ребер, Г – число областей).

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