Fórmula de la Suma de Grados

Teoría

La Fórmula de la Suma de Grados, que muchas veces vas a encontrar como el Lema del Apretón de Manos, es un resultado fundamental en la teoría de gráficas que relaciona el número de aristas de una gráfica con los grados de sus vértices. En cualquier gráfica no dirigida, el grado de un vértice lo definimos como el número de aristas que inciden en él. La fórmula dice que la suma de los grados de todos los vértices de una gráfica es igual al doble del número de aristas. Este resultado funciona para todas las gráficas no dirigidas, incluyendo gráficas simples y multigráficas (gráficas que permiten varias aristas entre los mismos vértices o lazos).

La intuición detrás de este teorema se basa en la técnica combinatoria de conteo doble. Imagina una arista que conecta al vértice $u$ con el vértice $v$. Cuando calculas el grado de $u$, cuentas esta arista una vez. Cuando calculas el grado de $v$, vuelves a contar la misma arista. Por lo tanto, cada arista aporta exactamente $2$ a la suma total de los grados: una vez por cada extremo. Si la gráfica tiene un lazo (una arista que conecta un vértice consigo mismo), esa arista aporta $2$ al grado de ese único vértice, así que la suma total se mantiene igual.

Este concepto es súper importante en las olimpiadas de matemáticas para determinar si ciertas gráficas pueden existir o no. Te da