Teorema de Fáry
En el campo matemático de la teoría de grafos, el teorema de Fáry establece que cualquier grafo plano simple puede ser dibujado sin cruces, de modo que todas sus aristas sean segmentos de recta. Es decir, la posibilidad de dibujar aristas curvas en lugar de segmentos de línea recta no permite dibujar una clase más grande de grafos. El teorema lleva el nombre de István Fáry, aunque fue demostrado de forma independiente por Klaus Wagner (1936),István Fáry (1948) y Sherman K. Stein (1951).
From Wikipedia, the free encyclopedia
En el campo matemático de la teoría de grafos, el teorema de Fáry establece que cualquier grafo plano simple puede ser dibujado sin cruces, de modo que todas sus aristas sean segmentos de recta. Es decir, la posibilidad de dibujar aristas curvas en lugar de segmentos de línea recta no permite dibujar una clase más grande de grafos. El teorema lleva el nombre de István Fáry, aunque fue demostrado de forma independiente por Klaus Wagner (1936),István Fáry (1948) y Sherman K. Stein (1951).
Una forma de probar el teorema de Fáry es usar el método de inducción:[1]
Sea G un grafo plano simple con n vértices; se pueden agregar aristas si es necesario para que G sea un grafo máximamente plano. Si n < 3, el resultado es trivial. Si n ≥ 3, entonces todas las caras de G deben ser triángulos, ya que se podría agregar una arista a cualquier cara con más lados conservando la planaridad, contradiciendo la suposición de planaridad máxima. Ahora, se eligen tres vértices a, b, c que formen una cara triangular de G. Se prueba por inducción sobre n que existe una reincrustación combinatoriamente isomorfa de G mediante segmentos rectos en la que el triángulo abc es la cara exterior de la incrustación ("combinatoriamente isomórfica" significa que los vértices, aristas y caras del nuevo dibujo se pueden hacer corresponder con los del dibujo anterior, de modo que todas las incidencias entre aristas, vértices y caras, no solo entre vértices y aristas, se conservan). Como caso base, el resultado es trivial cuando n= 3 y a, b y c son los únicos vértices en G. Así, se puede suponer que n ≥ 4.
Por la fórmula de Euler para grafos planos, G tiene 3n − 6 aristas. De manera equivalente, si se define la deficiencia de un vértice v en G como 6 − grado(v), la suma de las deficiencias es 12. Dado que G tiene al menos cuatro vértices y todas las caras de G son triángulos, se deduce que cada vértice en G tiene un grado de al menos tres. Por lo tanto, cada vértice en G tiene deficiencia como máximo tres, por lo que hay al menos cuatro vértices con deficiencia positiva. En particular se puede elegir un vértice v con cinco vecinos como máximo que sea diferente de a, b y c. Sea ahora G', que se obtiene quitando v de G y retriangulando la cara f formada quitando v. Por inducción, G' tiene una reintegración mediante segmentos rectos combinatoriamente isomórfica en la que abc es la cara exterior. Debido a que la reincrustación de G' era combinatoriamente isomorfa a G', al quitarle las aristas que se agregaron para crear G', queda la cara f, que ahora es un polígono P con cinco lados como máximo. Para completar el dibujo de un nueva incrustación isomórfica combinatoria mediante segmentos rectos de G, v debe colocarse en el polígono y unirse mediante líneas rectas a los vértices del polígono. Por teorema de la galería de arte, existe un punto interior a P en el que se puede colocar v de manera que las aristas desde v hasta los vértices de P no crucen ninguna otra arista, completando la prueba.
El paso de inducción de esta prueba se ilustra en la imagen de la derecha.
