El Teorema de Euler



El Teorema de Euler

Definición: Si un grafo se puede dibujar de modo que no se corten sus lados (aristas) excepto en los vértices se dice que es un grafo plano.





El grafo de lafigura es un grafo plano, porque aunque en la figura de la izquierda, las aristas se cortan en puntos distintos de los vértices, se puede encontrar un grafo isomorfo a él, el de la derecha, en el que lasaristas no se cortan. Cuando esté así dibujado, diremos que está representado apropiadamente.
Un grafo plano, apropiadamente representado divide al plano en distintas regiones llamadas caras. Si sedenota el número de caras por C, el número de vértices por V y el número de lados por A, en la figura se tiene que C = 4, V = 4 y A = 6.

Teorema de Euler:
En todo grafo conexo y plano que estéapropiadamente representado se verifica que el número de caras más el de vértices menos el de aristas vale 2. Es decir

C – A + V = 2.
Prueba
Para probar el teorema usamos el mismo razonamientoque ya empleamos en el problema de la red de volleyball: dado un grafo conexo y plano, como el de la figura, suprimimos lados hasta tener un árbol. En el proceso, el número de vértices permaneceinvariable, mientras que el número de lados disminuye de uno en uno mientras los vamos eliminando. Pero el número de caras también va disminuyendo de uno en uno. Fíjate que por cada lado que se elimina, doscaras se convierten en una. Entonces, la cantidad C – A + V permanece invariante en todo el proceso.
Claro que para un árbol ya sabemos que el número de vértices excede al de lados enuno, es decir V – A = 1, y como en un árbol hay una sola cara, V – A + C = 1 + 1 = 2. Y como ya se ha visto que para todos los grafos del proceso de eliminación de lados, incluido el grafo original, lacantidad C – A + V permanece invariante, se tiene la famosa fórmula de Euler:

C – A + V = 2.





Problema 1
En la ciudad de los lagos hay 7 lagos conectados por 10 canales, de modo...