Materia: #técnicas_y_diseños_de_algoritmos

Tags: Teorema, Grafos

Suma de grados de vértices de un grafo

Dado un grafo $G=(V,X)$, la suma de los grados de sus vértices es igual a 2 veces el número de sus aristas. Es decir:

Demostración:

Haremos inducción en la cantidad de aristas.

Caso base: El caso base de nuestra demostración es cuando $m$ es igual a $1$ (también podría haber sido $m=0$). En este caso el grafo $G$ solo tiene una arista, que notamos como $e=(u,w)$. Entonces $d(u)=d(w)=1$ y $d(v)=0$ para todo $v\in V$, con $v\ne u,w$. Por lo tanto $\sum _{v\in V}d(v)=2$ y $2m=2$, cumpliéndose la propiedad.

Paso inductivo: Para demostrar el paso inductivo, consideremos un grafo $G$ con $m$ aristas, con $m\ge 1$.

Nuestra hipótesis inductiva es: en todo grafo $G^{\prime }=(V^{\prime },X^{\prime })$ con $m^{\prime }<m$ aristas, se cumple que $\sum _{v\in V^{\prime }}{d}_{G^{\prime }}(v)=2m^{\prime }$.

Elijamos una arista $e=(u,w)$ cualquiera de nuestro grafo $G$, y llamemos $G^{\prime }$ al grafo que resulta si se la quitamos, esto es $G^{\prime }=(V,X^{\prime })$ con $X^{\prime }=X-\{e\}$.

Como la cantidad de aristas de $G^{\prime }$ es $m-1$, $G^{\prime }$ cumple la hipótesis de la $HI$. Entonces podemos aplicar la $HI$ sobre $G^{\prime }$:

Como $d_G(u)=d_{G^{\prime }}(u)+1$, $d_G(w)=d_{G^{\prime }}(w)+1$ y $d_G(x)=d_{G^{\prime }}(x)+1$ para todo $x\in V$, con $x\ne u,w$, obtenemos que:

Que es lo que queremos probar.