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$ противоречие. Значит, компонента одна, иными словами граф связен.