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

Представим города и дороги между ними в виде графа. Заметим, что в нем не может быть более трех компонент связности, поскольку иначе найдется компонента из одной вершины, а это противоречит условию о том, что из всякой вершины выходит ребро. Если компонент три, то в каждой ровно по 2 вершины (иначе есть компонента из одной вершины), значит, в каждой из компонент ровно одно ребро и всего их 3, а не 8. Пусть компоненты 2. Пусть в первой вершин. Тогда всего ребер не больше, чем . Но , а абсцисса вершины параболы , то есть максимальное значение равно противоречие. Значит, компонента одна, иными словами граф связен.