13 Grado y sucesion de grados ‣ Part IV Teoria de grafos ‣ Matemática discreta

Definition 13.1.

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$ .

Definition 13.2.

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$ .

Example 13.3.

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$ .

Theorem 13.4 (de Euler).

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

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

Proof 13.5.

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).

Corollary 13.6.

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

Proof 13.7.

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 (13.4),

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).

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.