Олимпиадные задачи из источника «глава 5. Графы» - сложность 1 с решениями

В классе больше 32, но меньше 40 человек. Каждый мальчик дружит с тремя девочками, а каждая девочка – с пятью мальчиками.

Сколько человек в классе?

В графе из каждой вершины выходит по три ребра. Может ли в нём быть 1990 рёбер?

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

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

  а) 8, 6, 5, 4, 4, 3, 2, 2?

  б) 7, 7, 6, 5, 4, 2, 2, 1?

  в) 6, 6, 6, 5, 5, 3, 2, 2?

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

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