¿Corrija la prueba no inductiva de la fórmula de Euler$|V|+|F|-|E|=2$?

Question

Teorema: El número de vértices $|V|$, bordes $|E|$, y se enfrenta a $|F|$ en un arbitrario conectado plano gráfico están relacionados por la fórmula $$|V|+|F|-|E|=2$$

Prueba De Intento:

(Para acíclicos grafos planares) Deje $G(V,E)$ ser un gráfico acíclico. Para cualquier línea-subgrafo $L=(V',E')$ de $G$, podemos comprobar fácilmente que $|V'|=2$, $|E'|=1$, e $|F'|=1$ donde $F'$ es la cara de un gráfico de línea. Por lo tanto, $|V'|+|F'|-|E'|=2$. Como construimos $G$ de $L$ mediante la adición de bordes, tenga en cuenta que para cada borde que añadir, podemos agregar un vértice así que, para cualquier número de aristas $n\in\Bbb{N}$ añadimos, también vamos a añadir $n$ vértices. Por lo tanto, $(|V'|+n)+|F'|-(|E'|+n)=|V|+|F|-|E|=2$.

(Para grafos planares con cíclico subdiagramas) El más pequeño de plano gráfico con una cíclico subgrafo es $C_3$(un triángulo). Claramente, cualquier plano gráfico con una cíclico subgrafo puede ser construido mediante la adición de más puntos y bordes a $C_3$. Podemos afirmar que para añadir un borde a $C_3$, que sea

1. Añadir un punto de $v^*$ en un borde de la $l$ que se 'divide' $l$ a dos diferentes bordes, a continuación, conecte $v^*$ a un vértice existente con una nueva arista; añade 2 bordes, 1 vértice, y 1 cara o

2. Conecta dos vértices existentes, que no están conectados por una arista, con una ventaja de nuevo; esto se suma a una cara o

3. Agregar 2 nuevos vértices con cada uno de ellos en un borde, a continuación, conecte los dos nuevos vértices con una ventaja de nuevo; esto agrega 2 vértices, 1 cara, y 3 bordes.

Sin embargo, observar que el método (1) y (3) de arriba es una combinación secuencial de dos muy primitivos pasos:

• Agregar un vértice existente en el borde.

• Conecta dos vértices existentes, que no están conectados por una arista, con un nuevo borde. (Este es el método (2) anteriormente.)

Nota:

• La adición de un punto a una perimetral existente implica $|V|+1$, $|E|+1$, e $|F|+0$.
• Método 2 implica $|V|+0$, $|E|+1$, e $|F|+1$.
• La adición de un punto fuera de cualquier borde nos obliga a conectar este nuevo vértice con un vértice existente por una nueva arista; esto implica $|V|+1$, $|E|+1$, e $|F|+0$.

Por lo tanto, la forma de numérico del parámetro de las variaciones que se producen cada vez que la construcción de un nuevo conectado plana gráfica es la siguiente:

• $(|V|+n)+|F|-(|E|+n)$
• $|V|+(|F|+m)-(|E|+m)$

Por lo tanto, $|V|+|F|-|E|=2$.

Answer 1

La prueba es no , un no-inductivo de la prueba. Los pasos en los que se construye $G$ a partir de un pequeño gráfico mediante la adición de bordes, y comprobar que $|V|-|E|+|F|=2$ aún mantiene debido a que la mano izquierda no cambia, son el inductivo pasos de su prueba.

Esto está muy bien! La inducción es grande. Pero están cayendo en el clásico "inducción trampa" que todo el mundo cae en la hora de escribir la inducción de pruebas acerca de los gráficos.

Siempre que se escribe un paso inductivo que "sube", a partir de un gráfico para que su resultado se da y lo que es más grande, que se han fijado el objetivo de mostrar que cada gráfico puede ser obtenida por el crecimiento de su base de caso en este camino. Usted no tiene cuidado acerca de esto:

• En el cíclico caso, escriba "Claramente, cualquier plano gráfico con una cíclico subgrafo puede ser construido mediante la adición de más puntos y bordes a $C_3$". Esto debería hacer sonar las alarmas. Siempre que se justifique intuitivamente clara declaración con "claridad", que no ha escrito una prueba.
• En el acíclicos caso, usted no ha declarado incluso la afirmación de que la prueba de necesidades para el trabajo: que cada árbol puede ser construido en varias ocasiones la adición de hojas de una línea de gráfico. (¿Te refieres a una ruta gráfica? Un gráfico de líneas es otra cosa.)

Podemos evitar el problema de la prueba de que estas duro-a-probar que las declaraciones por escrito inductivo paso que "va hacia abajo" en su lugar. Aquí, vamos a suponer que el resultado se mantiene para todos los pequeños gráficos, y tomar un poco más grande de gráfico, a continuación, eliminar un vértice o arista de, reduciéndolo a un gráfico en el que su hipótesis inductiva se aplica.

Por ejemplo, al probar fórmula de Euler para acíclicos gráficos, usted podría primer argumentar (en su forma favorita) que cualquier gráfico que contiene un vértice de grado $1$, a continuación, elimine ese vértice, junto con el borde de la misma. Esto reduce el gráfico a uno más pequeño para el que ya se ha verificado la fórmula de Euler.

Aquí, no hay que preocuparse de que hemos conseguido que todos los gráficos que estamos considerando en este caso, porque empezamos con un arbitrarios, gráfica.

Aparte de esto, su estrategia se ve bien. Usted sólo debe repensar sus argumentos en términos de la eliminación de una arista o vértice, en lugar de agregarlos.