В графе 125 вершин, все степени не менее 5. Докажите, что в этом графе найдётся цикл длины не более 6.

Чтобы доказать, что в графе с 125 вершинами, где все степени не менее 5, найдётся цикл длины не более 6, воспользуемся методом от противного и некоторыми свойствами графов. 1. **Определим граф**: Пусть \( G \) — граф с 125 вершинами, где степень каждой вершины \( \deg(v) \geq 5 \) для всех \( v \in V(G) \). 2. **Предположим, что в графе нет циклов длины 6 или меньше**: Это означает, что все циклы в графе имеют длину не менее 7. 3. **Рассмотрим подграфы**: Если в графе нет циклов длины 6 или меньше, то любой набор из 6 вершин может соединяться только с вершинами, которые находятся вне этого...