Definição

O grau, ou valência, $d_G(v) = d(v)$, de um vértice $v$ de um grafo $G = (V,A)$ qualquer, é o numero, $|A(v)|$, de arestas em $v$, ou seja o número de vizinho de $v$. Definimos: $d(v) = |N(v)|$, onde $N(v)$ é o conjunto dos vizinhos de $v$.