Dado el grafo nulo sin aristas ni vértices, tenemos un grafo plano conectado ya que no hay aristas que se crucen cuando este grafo se dibuja en el plano, y el hecho de que cualquier par de vértices distintos tenga un camino entre ellos es vacuamente cierto. Sin embargo, la fórmula de Euler no funciona: sustituyendo en $v+f= e+2$, tenemos $1=2$. ¿Por qué es esto así? ¿No podemos aplicar la fórmula de Euler aquí?
Respuesta
¿Demasiados anuncios?
Podemos generalizar ligeramente la fórmula de Euler como: $V-E+F-C = 1$, donde $C$ es el número de componentes. La mayor parte del tiempo $C=1$, lo que nos da la fórmula familiar. Pero funciona muy bien si $C>1$. Y la pregunta es sobre el caso "trivial" donde $C=0$. Ahora, por supuesto, $V=E=0$ y $F=1$, dándonos la respuesta correcta.
Hay una prueba estándar e inductiva de la fórmula de Euler que implica o bien quitar una arista y una cara, o quitar una arista y un vértice, y observar que el invariante permanece igual. Ver aquí. Pero estas pruebas son bastante complicadas, porque intentan preservar la conexidad.
Con la fórmula generalizada, la prueba puede ser mucho más limpia (aún omitiendo la topología elemental). Quitamos cualquier arista. Hay dos posibilidades disjuntas:
(1) Fusionamos dos caras distintas, así: $E-1; F-1$
(2) La arista siempre tenía la misma cara en ambos lados, por lo que quitar la arista divide una componente en dos: $E-1; C+1$
En cualquier caso, el invariante $V-E+F-C$ permanece igual. Así que quitamos todas las aristas, y luego tenemos un montón de vértices/componentes aislados en una sola cara, así que $V=C$ y por tanto $V-0+1-C = 1$.
Siempre es bueno cuando una fórmula se puede aplicar hasta llegar a $0$.
