Валентность

Количество ребер, инцидентных вершине v, называется валентностью (степенью) вершины v и обозначается d(v):

Минимальная степень вершины графа: δ(G);

Максимальная степень вершины графа: ∆(G).

0≤d(y)≤M - l

Если степени всех вершин равны k, то граф называется регулярнымстепени k:

δ(G) = (G) = k.

Степень регулярности является инвариантом графа и обозначается r(G). Для нерегулярных графов r(G) не определено.

Если степень вершины равна 0 (то есть d(v) = 0), то вершина называется изолиро­ванной. Если степень вершины равна 1 (то есть d(v) = 1), то вершина называется концевой, или висячей.

Если граф ориентированный, то говорят о полустепени захода (d+(v)) и полустепени исхода (d-(v)).

Теорема Эйлера: Сумма степеней вершин графа равна удвоенному количеству ребер.