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

### Решение задания 9 Пусть $K$ — количество кошек, а $M$ — количество мышек. Каждая кошка прогнала 4 мышки, значит, общее число связей (пар «кошка-мышка») равно $4K$. С другой стороны, каждая мышка убежала от 3 кошек, значит, это же число связей равно $3M$. Составим равенство: $4K = 3M$ Отсюда получаем соотношение: $K / M = 3 / 4$ Значит, на 3 кошки приходится 4 мышки. **Ответ:** Мышек больше. Графически это можно представить как двудольный граф, где одна доля (3 вершины) — кошки, а другая доля (4 вершины) — мышки. Из каждой «кошачьей» вершины выходит 4 ребра, а в каждую «мышиную» вершину входит 3 ребра. Общее количество ребер: $3 \times 4 = 12$ или $4 \times 3 = 12$. ### Решение задания 10 Если у нас есть 4 шарика, и каждый из них соединен с 3 другими, то общее число соединений можно найти по формуле для суммы степеней вершин графа (теорема о рукопожатиях). Сумма степеней вершин равна $4 \times 3 = 12$. Поскольку каждое ребро соединяет два шарика (участвуют две вершины), общее число ребер (ниток) должно быть $12 / 2 = 6$. Такой граф возможен: это полный граф $K_4$ (тетраэдр), где каждый из 4 шариков соединен со всеми остальными тремя. **Ответ:** Да, может. Это полный граф с 4 вершинами.