Упр.87 ГДЗ Бунимович Булычев 10 класс (Алгебра)

Рассмотрим вариант решения задания из учебника Бунимович, Булычев 10 класс, Просвещение: 87. В стране 13 городов, каждый из которых соединён авиасообщением с 6 другими. Докажите, что из любого города можно добраться в любой другой (возможно, с пересадками).

Рассмотрим граф, в котором вершины — это города, а рёбра — авиасообщения между ними. По условию в стране $$13$$ городов, и каждый город соединён с $$6$$ другими, значит степень каждой вершины равна $$6$$.

Предположим, что граф несвязный. Тогда его вершины можно разбить на несколько компонент связности. В каждой компоненте каждая вершина тоже имеет степень $$6$$, значит в компоненте должно быть не меньше $$7$$ вершин, иначе вершина не смогла бы быть соединена с $$6$$ другими городами внутри этой компоненты.

Но тогда при двух компонентах в графе было бы не меньше $$7+7=14$$ вершин, что невозможно, так как всего городов $$13$$. Следовательно, граф не может быть несвязным.

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

Ответ

Из любого города можно добраться в любой другой.