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$; pela definição de grafos, tal número é igual ao número de vizinhos de $v$. Definimos, então: $d(v) = |N(v)|$, onde $N(v)$ é o conjunto dos vizinhos de $v$.

Um vértice de grau $0$ é dito isolado.