13 Grado y sucesion de grados

Definición IV.5.

Se dice que dos vertices $u$ y $v$ de un grafo no dirigido $G=(V,E)$ son adyacentes si $\left\{u,v\right\}\in E$ . En ese caso se dice que la arista $e=\left\{u,v\right\}$ conecta los vertices $u$ y $v$ .

Definición IV.6.

Si $G=(V,E)$ es un (multi)grafo no dirigido y $u\in V$ , el grado del vertice $u$ es el numero de aristas incidentes con el, imponiendo por conveniencia que un lazo en un vertice contribuye dos veces al grado de ese vertice. Denotaremos el grado de un vertice $u$ por $gr(u)$ . Si un vertice tiene grado cero se dice que es un vertice aislado.

La sucesion de grados del grafo $G$ es la lista $\left\{gr(v_{1},),gr(v_{2}),\ldots,gr(v_{n})\right\}$ no ordenada de números, donde $v_{1},\ldots,v_{n}$ son todos los vertices de $V$ .

Ejemplo IV.2.

Considerense los grafos $G$ y $H$ de la figura. En el grafo $G$ se verifica que $gr(a)=3=gr(c)$ , $gr(b)=2=gr(e)$ y $gr(d)=4$ . En el grafo $H$ se verifica que $gr(f)=3$ , $gr(g)=2$ y $gr(h)=5$ .

Teorema IV.1 (de Euler).

Sea $G=(V,E)$ un grafo no dirigido. Se verifica que

\sum_{v\in V}gr(v)=2\cdot|E|

Demostración.

La demostracion es consecuencia de que cada arista contribuye dos veces a la suma de los grados de los vertices ya que una arista es incidente con exactamente dos vertices (que para los lazos son iguales). ∎

Corolario IV.1.

Cualquier grafo no dirigido tiene un numero par de vertices de grado impar.

Demostración.

Sean $V_{1}$ y $V_{2}$ los conjuntos de vertices de grado par e impar respectivamente del grafo $G=(V,E)$ .

$V_{1}$ y $V_{2}$ es particion de $V$ ya que $V=V_{1}+V_{2}$ y $V_{1}\cap V_{2}=\varnothing$ .

En ese caso, y aplicando el teorema de Euler (IV.1),

2|E|=\sum_{v\in V}gr(v)=\sum_{v\in V_{1}}gr(v)+\sum_{v\in V_{2}}gr(v)\text{ (% porque son una particion).}

o equivalentemente

2|E|-\sum_{v\in V_{1}}gr(v)=\sum_{v\in V_{2}}gr(v)\mathchar 46\relax

Puesto que para cada $v\in V_{1}$ se tiene que $gr(v)$ es un numero par y $2|E|$ es par entonces necesariamente $\sum\nolimits_{v\in V_{2}}gr(v)$ es un numero par. Por tanto, en el sumatorio debe haber una cantidad par de sumandos. ∎