15.2: Fórmula de Euler

A Euler se le ocurrió una fórmula que es válida para cualquier incrustación plana de un gráfico conectado.

Teorema\(\PageIndex{1}\)

Si\(G\) es una incrustación plana de una gráfica conectada (o multígrafo, con o sin bucles), entonces

\[|V | − |E| + |F| = 2.\]

Prueba 1:

Demostraremos esta fórmula por inducción en el número de caras de la incrustación. Let\(G\) Ser una incrustación plana de una gráfica conectada (o multígrafo, con o sin bucles).

Caso base: Si\(|F| = 1\) entonces\(G\) no puede tener ningún ciclo (de lo contrario el interior y el exterior del ciclo serían caras\(2\) distintas). Entonces\(G\) debe ser una gráfica conectada que no tenga ciclos, es decir, un árbol. Por el Teorema 12.4.1 sabemos que debemos tener\(|E| = |V | − 1\), así

\[|V | − |E| + |F| = |V | − (|V | − 1) + 1 = 2.\]

Un árbol no puede tener ningún bucle o múltiples aristas, ya que estos forman ciclos.

Paso inductivo: Comenzamos por exponer nuestra hipótesis inductiva. \(k ≥ 1\)Sea arbitrario, y supongamos que para cualquier incrustación plana de una gráfica conectada (o multígrafo, con o sin bucles) con\(k\) caras,\(|V | − |E| + |F| = 2\).

Let\(G\) Ser una incrustación plana de una gráfica conectada con\(k + 1 ≥ 2\) caras. Dado que los árboles tienen una sola cara,\(G\) deben tener un ciclo. Elija cualquier borde\(e\) que esté en un ciclo de\(G\), y deje\(H = G \setminus \{e\}\). Claramente, tenemos

\[|E(H)| = |E(G)| − 1\]

y\(|V (H)| = |V (G)|\). También,

\[|F(H)| = |F(G)| − 1 = k\]

ya que el borde\(e\) que forma parte de un ciclo debe separar dos caras de\(G\), las cuales están unidas en una cara de\(H\). Además, ya que\(e\) estaba en un ciclo y\(G\) está conectado, por la Proposición 12.3.4,\(H\) está conectado, y\(H\) tiene una incrustación plana inducida por la incrustación plana de\(G\). Por lo tanto, nuestra hipótesis inductiva se aplica a\(H\),

\[ \begin{equation} \begin{split} 2 &= |V (H)| − |E(H)| + |F(H)| \\ &= |V (G)| − (|E(G) − 1) + (|F(G)| − 1) \\ &= |V (G)| − |E(G)| + |F(G)| \end{split} \end{equation} \]

Esto completa el paso inductivo.

Por el Principio de Inducción Matemática,\(|V | − |E| + |F| = 2\) para cualquier incrustación plana de una gráfica conectada (o multígrafo, con o sin bucles).

La prueba anterior es inusual para una prueba por inducción en gráficas, porque la inducción no está en el número de vértices. Si intentas probar la fórmula de Euler por inducción sobre el número de vértices, eliminar un vértice podría desconectar la gráfica, lo que significaría que la hipótesis de inducción no se aplica a la gráfica resultante.

Sin embargo, hay una operación gráfica diferente que reduce el número de vértices en\(1\), y mantiene el gráfico conectado. Desafortunadamente, puede convertir una gráfica en un multígrafo, por lo que solo se puede usar para probar un resultado que sea válido tanto para multígrafos como para gráficas. Esta operación se llama contracción de borde.

Definición: Contraer el borde

Dejar\(G\) ser una gráfica con un borde\(uv\). La gráfica\(G'\) obtenida al contraer el borde\(uv\) tiene vértices.

\[V (G' ) = (V (G) \setminus \{u, v\}) ∪ \{u' \},\]

donde\(u'\) hay un nuevo vértice. Los bordes son

\[E(G') = \left( [E(G) \setminus \{ux : ux ∈ E(G)\}] \setminus \{vx : vx ∈ E(G)\} \right) ∪ \{u'y | uy ∈ E(G) \text{ or } vy ∈ E(G)\}\]

Si piensas en vértices\(u\) y\(v\) como estar conectado por un elástico muy corto que se ha estirado en\(G\), entonces puedes pensar en\(G'\) como la gráfica que obtienes si permites que el elástico se contraiga, combinando los vértices\(u\) y\(v\) en un vértice “nuevo” \(u'\).

Observe que si\(G\) está conectado, entonces también se\(G\) conectará la gráfica obtenida al contraer cualquier borde de. Sin embargo, si\(uv\) es el borde que contratamos,\(u\) y y\(v\) tenemos un vecino mutuo\(x\), entonces en la gráfica obtenida por la contratación\(uv\), habrá una arista múltiple entre\(u'\) y\(x\). Además, si\(G\) tiene una incrustación plana, entonces después de contraer cualquier borde todavía habrá una incrustación plana. Si\(u \neq v\), entonces la contracción\(uv\) reduce el número de vértices en uno, reduce el número de aristas en uno, y no cambia el número de caras.

Ahora podemos usar esta operación para probar la fórmula de Euler por inducción en el número de vértices

Teorema\(\PageIndex{1}\)

Si\(G\) es una incrustación plana de una gráfica conectada (o multígrafo, con o sin bucles), entonces

\[|V | − |E| + |F| = 2.\]

Prueba 2:

Let\(G\) Ser una incrustación plana de una gráfica conectada (o multígrafo, con o sin bucles).

Caso base: Si\(|V | = 1\) entonces\(G\) tiene un vértice. Además, cada borde es un bucle. Cada bucle implica\(1\) borde, y encierra\(1\) la cara. Por lo tanto, esta gráfica tendrá una cara más de la que tiene bucles (ya que tiene una cara aunque no haya bucles). Por lo tanto,

\[|V | − |E| + |F| = 1 − e + (e + 1) = 2.\]

Paso inductivo: Comenzamos por exponer nuestra hipótesis inductiva. \(k ≥ 1\)Sea arbitrario, y supongamos que para cualquier incrustación plana de una gráfica conectada (o multígrafo, con o sin bucles) con\(k\) vértices,\(|V | − |E| + |F| = 2\).

Let\(G\) Ser una incrustación plana de una gráfica conectada con\(k + 1 ≥ 2\) vértices. Dado que la gráfica está conectada y tiene al menos dos vértices, tiene al menos un borde\(uv\), con\(u \neq v\). \(G'\)Sea la gráfica que obtengamos contratando\(uv\). Entonces\(G'\) es una incrustación plana de una gráfica conectada (o multígrafo, con o sin bucles) en\(k\) vértices, por lo que nuestra hipótesis inductiva se aplica a\(G'\). Por lo tanto,

\[ \begin{equation} \begin{split} 2 &= |V (G')| − |E(G')| + |F(G')| \\ &= (|V (G)| − 1) − (|E(G) − 1) + |F(G)| \\ &= |V (G)| − |E(G) + |F(G)| \end{split} \end{equation} \]

Esto completa el paso inductivo.

Por el Principio de Inducción Matemática,\(|V | − |E| + |F| = 2\) para cualquier incrustación plana de una gráfica conectada (o multígrafo, con o sin bucles).

La contracción de bordes tiene algunos otros usos muy importantes en la teoría de grafos. Antes de ver algunos corolarios de la Fórmula de Euler, explicaremos un teorema bien conocido que involucra contracción de bordes y gráficos planos.

Definición: Menor

\(G\)Déjese ser una gráfica. Entonces\(H\) es menor de\(G\) si podemos construir\(H\) a partir de\(G\) borrando o contrayendo bordes y eliminando vértices.

En 1937, Wagner demostró un teorema bastante similar al de Kuratowski.

Teorema\(\PageIndex{2}\): Wagner's Theorem

Una gráfica es plana si y sólo si no tiene isomórfica menor a\(K_5\) o\(K_{3,3}\).

Es posible probar el Teorema de Wagner como una consecuencia fácil del Teorema de Kuratowski, ya que si\(G\) tiene una subgrafía que es una subdivisión de\(K_5\) o\(K_{3,3}\) luego contraer todas menos una pieza de cada borde subdividido nos da un menor que es isomórfico a\(K_5\) o\(K_{3,3}\). No obstante, el Teorema de Wagner es importante por derecho propio, como primer ejemplo de la obra mucho más reciente y muy poderosa de Neil Robertson y Paul Seymour sobre menores de gráfica.

Se dice que una familia está menor cerrada si se le da alguna gráfica en la familia, cualquier menor de la gráfica también está en la familia. Las gráficas planas son un ejemplo de una familia cerrada menor, ya que las operaciones de eliminación (de aristas o vértices) y contracción de aristas conservan una incrustación plana. Robertson y Seymour demostraron el notable resultado de que si una familia de gráficas es menor cerrada, entonces la familia puede caracterizarse por un conjunto finito de “menores prohibidos”. Es decir, para cualquier familia de este tipo\(\mathcal{F}\), existe un conjunto finito\(\mathcal{L}\) de gráficas, de tal manera que\(\mathcal{G} ∈ \mathcal{F}\) si y sólo si no\(\mathcal{G}\) aparece menor de en\(\mathcal{L}\). El teorema de Wagner nos dice que cuando\(\mathcal{F}\) es la familia de las gráficas planas,\(\mathcal{L} = \{K_5, K_{3,3}\}\).

La Fórmula de Euler tiene algunos corolarios importantes.

Corolario\(\PageIndex{1}\)

Dejar\(G\) ser una gráfica conectada. Entonces, cada incrustación plana de\(G\) tiene el mismo número de caras.

Prueba

Nosotros tenemos\(|V | − |E| + |F| = 2\). Dado que\(|V|\) y\(|E|\) no dependemos de la elección de incrustación,\(|F| = 2 + |E| − |V|\) no hemos podido depender de la elección de incrustación.

Corolario\(\PageIndex{2}\)

Si\(G\) es un simple gráfico plano conectado y\(|V| ≥ 3\), entonces

\[|E| ≤ 3|V| − 6\]

Si además, no\(G\) tiene ciclos de longitud inferior a\(4\), entonces\(|E| ≤ 2|V| − 4\).

Prueba

Arreglar una incrustación plana de\(G\). Nos movemos alrededor de cada cara, contando el número de aristas que encontramos, y resolvemos el resultado de dos maneras.

Primero, miramos cada cara a su vez y contamos cuántos bordes rodean esa cara. Dado que la gráfica es simple, cada cara debe estar rodeada por al menos\(3\) bordes a menos que haya una sola cara. Si solo hay una cara y al movernos por esta cara no contamos al menos\(3\) aristas, entonces la gráfica es un árbol que tiene como máximo un borde, entonces\(|V| ≤ 2\). Por lo tanto, nuestro conteo llegará a por lo menos\(3|F|\).

Cada borde separa dos caras o se coloca en una cara. En el primer caso, se contará una vez cada vez que nos movemos alrededor de una de las dos caras de incidente. En este último caso, se contará dos veces a medida que nos movemos alrededor de la cara en la que colgaba: una vez cuando nos movemos hacia adentro por esta parte colgando, y otra cuando retrocedamos hacia afuera. Así, cada borde se cuenta exactamente dos veces, por lo que nuestro conteo llegará exactamente a\(2|E|\).

Combinando estos, vemos eso\(2|E| ≥ 3|F|\), así\(|F| ≤ \dfrac{2|E|}{3}\). Si no\(G\) tiene ciclos de longitud menor que\(4\), entonces cada cara debe estar rodeada por al menos\(4\) aristas, así que el mismo argumento da\(2|E| ≥ 4|F|\), entonces\(|F| ≤ \dfrac{|E|}{2}\).

Por la Fórmula de Euler,\(|V| − |E| + |F| = 2\), so

\[|V| − |E| + \dfrac{2|E|}{3} ≥ 2.\]

Multiplicando por\(3\) y moviendo los\(|E|\) términos hacia el lado derecho, da

\[3|V| ≥ |E| + 6,\]

que se puede reorganizar fácilmente en la forma de nuestra declaración original. En el caso donde no\(G\) tiene ciclos de longitud menor que\(4\), obtenemos en su lugar

\[|V| − |E| + \dfrac{|E|}{2} ≥ 2,\]

así\(2|V| ≥ |E| + 4\), que de nuevo se puede reorganizar fácilmente en la forma que se da en el enunciado de este corolario.

Corolario\(\PageIndex{3}\)

Si\(G\) es un simple gráfico plano conectado, entonces\(δ(G) ≤ 5\).

Prueba

Hacia una contradicción, supongamos que\(G\) es una simple gráfica plana conectada, y para cada\(v ∈ V\),\(d(v) ≥ 6\). Entonces

\[\sum_{v∈V} d(v) ≥ 6|V|.\]

Por el lema de apretón de manos de Euler, esto da

\[\sum_{v∈V} d(v) = 2|E| ≥ 6|V |.\]

Por lo tanto,

\[|E| ≥ 3|V | > 3|V | − 6,\]

pero esto contradice el Corolario 15.2.2.

La Fórmula de Euler (y sus corolarios) nos dan una manera mucho más fácil de demostrarlo\(K_5\) y no\(K_{3,3}\) son planares.

Corolario\(\PageIndex{4}\)

La gráfica no\(K_5\) es plana.

Prueba

En\(K_5\) tenemos\(|E| = \binom{5}{2} = 10\), y\(|V| = 5\). Entonces,

\[3|V| − 6 = 15 − 6 = 9 < 10 = |E|\]

Por Corolario 15.2.2, no\(K_5\) debe ser plano.

Corolario\(\PageIndex{5}\)

La gráfica no\(K_{3,3}\) es plana

Prueba

En\(K_{3,3}\) tenemos\(|E| = 9\), y\(|V| = 6\). Entonces,

\[2|V | − 4 = 12 − 4 = 8 < 9 = |E|\]

Ya que\(K_{3,3}\) es bipartita, no tiene ciclos de longitud menor que\(4\), por lo que por Corolario 15.2.2, no\(K_{3,3}\) debe ser planar

Ejercicio\(\PageIndex{1}\)

1) Utilice la inducción para probar una fórmula similar a Euler para gráficos planos que tengan exactamente dos componentes conectados.

2) La fórmula de Euler se puede generalizar a gráficos desconectados, pero tiene una variable extra para el número de componentes conectados de la gráfica. Adivina cuál será esta fórmula, y usa la inducción para probar tu respuesta.

3) Encontrar y probar un corolario a la fórmula de Euler para gráficas desconectadas, similar al Corolario 15.2.2. (Usa tu respuesta a la pregunta\(2\).)

4) Para gráficas incrustadas en un toro,\(|V| − |E| + |F|\) tiene un valor diferente (pero constante), siempre y cuando todas las caras “parezcan” discos. (Si está familiarizado con la topología, las caras deben ser incrustables en un plano, en lugar de verse como un toro. Entonces, poner una incrustación plana de una gráfica hacia abajo en un lado de un toro no cuenta.) ¿Cuál es este valor?

5) Definición. Decimos que una incrustación plana de una gráfica es auto-dual si es isomórfica a su dual planar. Demostrar que si una incrustación plana de la gráfica conectada\(G\) es auto-dual, entonces\(|E| = 2|V| − 2\).

6) Definición. El complemento de\(G\) es la gráfica con los mismos vértices que\(G\), pero cuyos bordes son precisamente los no bordes de\(G\). (Es decir,\(u\) es adyacente a\(v\) en el complemento de\(G\) si y solo no\(u\) es adyacente a\(v\) in\(G\).) Por lo tanto, si\(G^c\) es el complemento de\(G\), entonces\(E(K_{|V(G)|})\) es la unión disjunta de\(E(G)\) y\(E(G^c)\). Mostrar que si\(G\) es una gráfica plana simple con al menos once vértices, entonces el complemento de no\(G\) es plano.

7) Encuentra una gráfica plana\(G\) con\(|V| = 8\) cuyo complemento también sea plano.

8) Para cada uno de los siguientes conjuntos de condiciones, ya sea dibuje una gráfica simple y conectada\(G\) en el plano que satisfaga las condiciones, o bien explique cómo sabes que no hay una.

(a) La gráfica tiene\(15\) vértices y\(12\) aristas.

(b) La gráfica tiene\(10\) vértices y\(33\) aristas.

(c) La gráfica tiene\(5\) vértices y\(8\) aristas.

(d) La gráfica tiene\(6\) vértices y\(9\) aristas, y la incrustación tiene 6 caras