¿Funciona este ejemplo de "inducción inversa"?

Question

Digamos que hemos demostrado que alguna afirmación $P(1)$ es cierto. Supongamos que podemos demostrar $P(m) \iff P(m-1)$ . Entonces, habremos demostrado $P(m) \iff P(1)$ Así que $P(m)$ es cierto. Esto tiene sentido, ¿verdad?

Así que, con más contexto, digamos que nos gustaría mostrar un gráfico que depende de $n$ con determinadas propiedades. Entonces, si demostramos que existe para $n = 1$ y a continuación demostramos que si existe un grafo para arbitrary $n$ entonces podemos obtener el $n-1$ caso mediante supresiones de aristas/vértices, ¿podemos decir que es válido para todos los $n \in \mathbb{N}$ ? Para ser más precisos, ¿es esta supresión general de vértices y aristas un "proceso reversible"?

Answer 1

Teorema falso. Para todos $n$ existe un grafo simple con $n$ vértices y $n^2-1$ bordes.

Prueba. Esto existe para $n=1$ toma el gráfico con $1$ vértice y ninguna arista.

Supongamos que existe para $n$ vértices. Entonces, borrando un vértice de algún grado $k$ y, a continuación, eliminar $(2n-1)-k$ más aristas arbitrariamente, obtenemos un grafo simple con $n-1$ vértices y $(n-1)^2-1$ bordes.

---

Este es un ejemplo del problema. En general, borrar cosas no es reversible, ya que puedes acabar pasando de un grafo imposible a un grafo posible borrando los lugares donde es imposible. Incluso en los casos en que es reversible, tu prueba sería más limpia si construyeras las gráficas "hacia delante" en lugar de "hacia atrás".

Answer 2

En tu primer párrafo, has afirmado mostrando implicación en ambas direcciones y la afirmación tiene sentido. De hecho, la implicación hacia adelante es el caso estándar en la inducción normal

Sin embargo, en tu segundo párrafo, sólo has mostrado una implicación para la dirección inversa. Sólo se puede afirmar que si se demostró el caso de algunos fijos $k$ y si $P(k)\implies P(k-1)$ la afirmación es válida para todos los $n\leq k$ . Esto se conoce como inducción hacia atrás. No se puede decir nada sobre $n>k$ .

(Corrígeme si mi interpretación de lo que querías decir es errónea. Porque si lo que quieres demostrar es la existencia de una gráfica y has demostrado que existe una gráfica para alguna arbitraria $k$ no necesitas inducción?)

Otra técnica común de inducción en grafos es Inducción hacia delante y hacia atrás .