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

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

Задача 3: В двудольном графе сумма степеней вершин каждого цвета равны между собой.

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

Задача 5: Какое наибольшее число ребер может быть в двудольном графе с b белыми и r черными вершинами?

Задача 6: Какое наибольшее число ребер может быть в двудольном графе а) с 2n вершинами; б) с 2n+1 вершиной?

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

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

Задача 9: Докажите, что в двудольном графе нет нечетных циклов.

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

Задача 11: Пусть  Γ  – двудольный граф с черными и белыми вершинами. а) Если в  Γ  есть замкнутый цикл, проходящий через каждую вершину ровно по одному разу, то вершин каждого цвета – поровну. б) Если в  Γ  есть путь, проходящий через каждую вершину ровно по одному разу, то что число белых вершин отличается от числа черных вершин не более чем на 1.

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

Задача 13: Несколько равносторонних треугольников на плоскости не перекрываются. Всегда ли можно раскрасить их в два цвета так, чтобы треугольники с общим отрезком границы были разного цвета?

Задача 14: Докажите, что дерево – двудольный граф.

Задача 15: (критерий двудольного графа) Граф – двудольный если и только если нём нет нечетных циклов.

Задача 16: При каких n можно в вершинах n-угольника расставить натуральные числа так, чтобы на каждой стороне одно число делилось на другое, а для всех остальных пар чисел такого не было?

Задача 17: а) В клетки доски 8 × 8 записали числа 1, 2, …, 64 в неизвестном порядке. Разрешается узнать сумму чисел в любой паре клеток с общей стороной. Всегда ли можно узнать расположение всех чисел? б) То же для доски 9 × 9.

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

Задача 19: Гриша записал в клетки шахматной доски числа 1, 2, …, 64 в неизвестном порядке. Он сообщил Леше сумму чисел в каждом прямоугольнике из двух клеток и добавил, что 1 и 64 лежат на одной диагонали. Докажите, что по этой информации Леша может точно определить, где какое число записано.

Задача 20: Вершины конечного графа как-то пронумеровали от 1 до n, затем на каждом ребре записали сумму номеров в его концах, а номера в вершинах стерли. Докажите, что

а) Если граф не двудольный, то нумерация однозначно восстанавливается.

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