13 Grado y sucesion de grados

Definición 13.1.

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

Definición 13.2.

Si G=(V,E)\displaystyle G=(V,E) es un (multi)grafo no dirigido y u∈V\displaystyle u\in V, el grado del vertice u\displaystyle 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\displaystyle u por g⁢r⁢(u)\displaystyle gr(u). Si un vertice tiene grado cero se dice que es un vertice aislado. La sucesion de grados del grafo G\displaystyle G es la lista {gr(v1,),gr(v2),…,gr(vn)}\displaystyle\{gr(v_{1},),gr(v_{2}),\ldots,gr(v_{n})\} no ordenada de números, donde v1,…,vn\displaystyle v_{1},\ldots,v_{n} son todos los vertices de V\displaystyle V.

Ejemplo.

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

Teorema 13.1 (de Euler).

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

∑v∈Vg⁢r⁢(v)=2⋅|E|\displaystyle\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 13.1.

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

Demostración.

Sean V1\displaystyle V_{1} y V2\displaystyle V_{2} los conjuntos de vertices de grado par e impar respectivamente del grafo G=(V,E)\displaystyle G=(V,E). V1\displaystyle V_{1} y V2\displaystyle V_{2} es particion de V\displaystyle V ya que V=V1+V2\displaystyle V=V_{1}+V_{2} y V1∩V2=∅\displaystyle V_{1}\cap V_{2}=\varnothing. En ese caso, y aplicando el teorema de Euler (13.1),

2⁢|E|=∑v∈Vg⁢r⁢(v)=∑v∈V1g⁢r⁢(v)+∑v∈V2g⁢r⁢(v)⁢ (porque son una particion).\displaystyle 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|−∑v∈V1g⁢r⁢(v)=∑v∈V2g⁢r⁢(v).\displaystyle 2|E|-\sum_{v\in V_{1}}gr(v)=\sum_{v\in V_{2}}gr(v).

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