Question

Можно ли соединить 13 городов дорогами так чтобы из каждого города выходило 5 дорог

Answer 1

Ответ: нет, каждую дорогу считаем дважды, поэтому общее количество дорог должно быть чётным. В этом случае 13*5=65.

Answer 2

Нет, нельзя соединить 13 городов дорогами таким образом, чтобы из каждого города выходило ровно 5 дорог.

Для того, чтобы каждый город имел ровно 5 дорог, нужно иметь общее количество дорог, равное 13 умножить на 5, то есть 65 дорог.

Однако, в любом связном графе с нечетным количеством вершин (городов) количество ребер (дорог) всегда будет четным. В нашем случае 13 - нечетное число, следовательно, количество ребер не может быть равным 65, а может быть только четным числом.

Поэтому, не существует способа соединить 13 городов дорогами таким образом, чтобы из каждого города выходило ровно 5 дорог.