Grado de un vértice

Para calcular el grado basta contar los extremos de arista que caen sobre el vértice. En un grafo simple el grado de \(v\) coincide con el número de vecinos de \(v\), y siempre cumple \(0\le \deg(v)\le n-1\) si el grafo tiene \(n\) vértices. Un vértice de grado \(0\) es aislado y uno de grado \(1\) se llama hoja.

El resultado básico es el lema del apretón de manos: la suma de los grados de todos los vértices es \(\sum_{v\in V}\deg(v)=2|E|\), porque cada arista aporta una unidad a cada uno de sus dos extremos. De aquí se sigue que la cantidad de vértices de grado impar es siempre par.

El lema sirve de filtro: una lista de números solo puede ser la lista de grados de un grafo simple si su suma es par y si ningún grado supera \(n-1\). Ese criterio es necesario pero no suficiente; por ejemplo, \(3,3,3,1\) pasa ambas pruebas y aun así no corresponde a ningún grafo simple, porque tres vértices de grado \(3\) alcanzan al cuarto.

Un error frecuente es contar las aristas en lugar de los extremos: en un grafo simple no hay diferencia, pero en multigrafos con lazos un lazo cuenta dos veces. El grado es la base para hablar de grafos regulares (todos los vértices con el mismo grado), como \(K_n\), y para los caminos eulerianos que veremos después.