Question

4. В стране 6 городов и 8 дорог, соединяющих эти города (каждая дорога соединяет два города; из одного города в другой есть не более одной дороги). Также известно, что из каждого города выходит хотя бы одна дорога. Докажите, что из каждого города можно попасть в любой другой город,​

Answer 1

Представим города и дороги между ними в виде графа. Заметим, что в нем не может быть более трех компонент связности, поскольку иначе найдется компонента из одной вершины, а это противоречит условию о том, что из всякой вершины выходит ребро. Если компонент три, то в каждой ровно по 2 вершины (иначе есть компонента из одной вершины), значит, в каждой из компонент ровно одно ребро и всего их 3, а не 8. Пусть компоненты 2. Пусть в первой $k$ вершин. Тогда всего ребер не больше, чем $\frac{k(k-1)}{2}+\frac{(6-k)(5-k)}{2} = k^2-6k+15$. Но $k\in[2,4]$, а абсцисса вершины параболы $k=3$, то есть максимальное значение равно $2^2-6\cdot 2+15=7$ противоречие. Значит, компонента одна, иными словами граф связен.

Answer 2

Для доказательства того, что из каждого города можно попасть в любой другой город, давайте воспользуемся принципом математической индукции.

Для начала, предположим, что это верно для страны с 6 городами и 8 дорогами. Теперь давайте рассмотрим новый город и соединим его с каждым из 6 существующих городов новой дорогой. Это добавит к нашей системе 6 новых дорог, и теперь у нас будет 7 городов и 14 дорог.

Мы знаем, что из каждого города выходит хотя бы одна дорога, и мы только что добавили новый город, так что у нас всегда есть по крайней мере одна дорога из каждого города. Теперь у нас есть 7 городов и 14 дорог, и мы предположили, что из каждого города можно попасть в любой другой город в стране с 6 городами и 8 дорогами.

Теперь рассмотрим каждый из оставшихся 6 городов в этой новой системе. Мы знаем, что из каждого из них есть хотя бы одна дорога, и мы также добавили по одной дороге от каждого из них к остальным 6 городам. Таким образом, из каждого из этих 6 городов можно попасть в любой из 7 городов в системе.

Мы успешно доказали, что в стране с 7 городами и 14 дорогами, из каждого города можно попасть в любой другой город. Теперь мы можем применить индукцию и заключить, что это верно и для исходной страны с 6 городами и 8 дорогами.