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