В компании из \(\displaystyle 10\) человек выяснилось, что семеро пришедших обменялись рукопожатиями с шестью другими среди собравшихся, а оставшиеся трое совершили по \(\displaystyle 5\) рукопожатий.
Может ли такое быть?
Представим, что люди – это вершины графа, а знакомства – рёбра. То есть две вершины соединены ребром, если соответствующие люди знакомы.
Тогда из вершины выходит столько рёбер, сколько знакомых имеет данный человек среди собравшихся.
Так как
Степенью (порядком, валентностью) вершины графа называется количество рёбер, исходящих из этой вершины.
то в данном графе степень вершины – это и есть количество знакомых.
Таким образом, имеем граф на \(\displaystyle 10\) вершин, в котором степень семи вершин равна \(\displaystyle 6{\small,}\) а степень оставшихся трёх вершин равна \(\displaystyle 5{\small.}\)
Найдём сумму степеней всех вершин данного графа:
\(\displaystyle 7 \cdot6+3\cdot5=42+15=57{\small.}\)
Воспользуемся теоремой
Теорема о сумме степеней вершин
В любом графе сумма степеней всех вершин является чётным числом.
То есть графа с нечетной суммой степеней вершин не существует.
Значит, и компании из \(\displaystyle 10\) человек, в которой семеро пришедших обменялись рукопожатиями с шестью другими среди собравшихся, а оставшиеся трое совершили по \(\displaystyle 5\) рукопожатий, быть не может.
Ответ: нет.