Тема 2. Степени вершин графа

Задание 1. Изобразите граф со следующим набором степеней вершин: ; ; ; ; ; .

Задание 2. Докажите, что число перекрестков любого города, в которых встречается нечетное число улиц – чётно.

Задание 3. Марсиане рождаются с произвольным (конечным) количеством рук. Если все марсиане возьмутся за руки, то свободных рук не останется. Докажите, что количество марсиан с нечётным числом рук чётно.

Задание 4. В классе 30 человек. Может ли быть так, что 9 из них имеют по 5 друзей, 11 человек – по 4 друга, а 10 – по 3?

Задание 5. В офисе 15 телефонов. Можно ли соединить их между собой так, чтобы каждый был соединен с 3 другими?

Задание 6. В елочной гирлянде каждая жёлтая лампочка соединена с 10 красными, а каждая красная – с 8 жёлтыми. Сколько красных и сколько жёлтых лампочек в гирлянде, если общее число лампочек равно 180?

Задание 7. Можно ли изобразить на плоскости 9 прямых так, чтобы каждая из них пересекалась ровно с пятью другими?

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

Задание 9. Существует ли многогранник с нечётным числом граней, все грани которого – многоугольники с нечётным числом сторон?

Задание 10. На некотором факультете обучаются 1055 студентов. Некоторые из них знакомы друг с другом. Докажите, что хотя бы у одного из них число знакомых среди студентов этого факультета чётно.

Задание 11. Можно ли построить город, на каждом перекрестке которого «встречалось» бы разное число улиц? Равное число улиц?

Задание 12. Постройте граф общего вида (ориентированный, с параллельными ребрами или петлями) на четырёх вершинах, в котором все вершины имеют разные степени.

Задание 13. Найдите суммы степеней вершин графов: тел Платона (тетраэдра, куба, октаэдра, додекаэдра, икосаэдра); Петерсена.

Задание 14. Графом коктейльной партии называется граф , где ,

Например, графы коктейльной партии для имеют вид

Найдите суммы степеней вершин для каждого из графов и докажите, что при любом натуральном n сумма степеней вершин графа коктейльной партии равна .