.

Привет! Давай посмотрим на эту задачку вместе.

Условие задачи говорит нам о том, что в маленькой деревне всего 35 домов, и спрашивает нас, может ли быть так, что у каждого дома 6, 8 или 10 соседей. Задача просит нас понять, возможно ли так расположить дома, чтобы у каждого дома было указанное количество соседей.

Сложность тут в том, что дома не могут иметь случайное количество соседей; это число должно быть либо 6, либо 8, либо 10.

Прежде всего важно понять, что количество соседей у домов – это по сути степень вершин в графе. И тут возникает понятие рукопожатий в графе: сумма степеней всех вершин равна удвоенному количеству рёбер.

То есть, если у каждого дома минимум 6 соседей, то общее количество рукопожатий должно быть не меньше чем \( 6 \times 35 \). Но в то же время, если учесть, что у некоторых домов 8, а у некоторых 10 соседей, общее количество рукопожатий должно быть еще больше.

Для того чтобы у всех домов было 6 соседей, необходимо, чтобы каждый дом был соединен с каждым. Но при этом получится, что у каждого дома будет не 6 соседей, а 34 (ведь из 35 домов нужно исключить сам дом).

Теперь давай подумаем насчет 8 и 10 соседей.