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

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

Степенью (валентностью) вершины называется число ребер графа, которым принадлежит эта вершина, обозначается $d(V_i)$.

Вершина графа, для которой $d(V_i) = 0$, является изолированной, для которой $d(V_i) = 1$ — висячей.

В графе $G = (V, E)$ сумма степеней всех его вершин равна удвоенному числу его ребер, $$\sum^{n}_{i=1} {d(V_i)} = 2|E|$$