Estoy teniendo problemas con este problema de Trudeau Introducción a la Teoría de grafos y agradecería alguna pista.
Probar este parcial conversar de la Fórmula de Euler: si un grafo es planar y $v+f-e=2$, entonces la gráfica está conectado.
He aquí lo que he probado hasta ahora:
El problema me pide para demostrar que un enunciado de la forma $A \wedge B \implies C$, donde:
- $A$ significa que el grafo es planar
- $B$ $v+f-e=2$
- $C$ significa que la gráfica está conectado
Parece difícil de probar $C$ para cualquier gráfico, así que formó el contrapositivo declaración: Si un grafo es desconectado, entonces la gráfica es nonplaner o $v+f-e \neq 2$. Así que ahora estoy tratando de demostrar que $\neg C \implies (\neg A \vee \neg B)$.
Me llamó ejemplo los gráficos que están desconectados, plana, y en todos los ejemplos que se me ocurrió, $v+f-e \neq 2$. Esto sugiere que la $\neg C \wedge A \implies \neg B$. Si yo pudiera probar esto, entonces creo que esto es equivalente a una prueba de $\neg C \implies (\neg A \vee \neg B)$, la cual es equivalente a una prueba de $A \wedge B \implies C$. Pero estoy atascado aquí.
Es el contrapositivo enfoque incluso un útil? Hay otros consejos sobre cómo podría enfoque de la prueba?
