Euler Teorema

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.

[pic]El grafo de la figura 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 laderecha, en el que las aristas no se cortan. Cuando esté así dibujado, diremos que está representado apropiadamente.
Un grafo plano, apropiadamente representado divide al plano en distintasregiones llamadas caras. Si se denota 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 grafoconexo 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 teoremausamos el mismo razonamiento que 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úmerode vértices permanece invariable, 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 porcada lado que se elimina, dos caras 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 devértices excede al de lados en uno, 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, la cantidad 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...