Степень вершины

Количество рёбер, выходящих из одной вершины графа, называется степенью этой вершины.
Сумма степеней всех вершин графа равна удвоенному числу его рёбер.
Для любого графа количество вершин нечётной степени всегда чётно.
В любом графе есть по крайней мере две вершины, имеющие одинаковую степень.
Пример. Встретились 12 друзей и каждый с каждым обменялся рукопожатием. Сколько всего рукопожатий было?
Решение.
Можно изобразить эту ситуацию в виде: друзья – вершины, рукопожатия – рёбра. Тогда из каждой вершины будет выходить 11 рёбер, то есть степень каждой вершины равна 11.
Теперь нетрудно подсчитать количество рёбер: (12 $\cdot$ 11) : 2 = 66.
Ответ: 66 рукопожатий.

Было полезно?