Concepto de prueba por contradicción

Question

Debería probarlo por contradicción:

Un gráfico $G$ tiene vértices de los cuales todos tienen grado de al menos $2$ . Demostrar que $G$ contiene un ciclo.

Así que pensé: Demostrar: si un gráfico $G$ tiene vértices todos ellos de grado $0$ o $1$ Entonces, ¿tiene un ciclo?

¿Entonces cuando no pueda conseguir un ciclo demostrará la afirmación original? Pero eso no suena como una prueba.

Answer 1

Efectivamente, eso no es una prueba. El hecho de que puedas demostrar que un grafo en el que todos los vértices tienen un grado de 0 y 1 no tiene un ciclo no implica que todo grafo en el que todos los vértices tienen un grado de 2 o superior deba tener un ciclo. Básicamente estás cometiendo la falacia lógica de Negar el Antecedente:

$P \to Q$

$\therefore \neg P \to \neg Q$

No es una inferencia válida: Supongamos que soy feliz si me toca la lotería... ¿Significa eso que no soy feliz cuando no me toca la lotería? No.

Y por cierto, la negación de que todos los vértices tengan grado 2 o superior no es que todos los vértices tengan grado 0 o 1. La negación sería que hay un peu de vértice con un grado de 0 o 1.

Esto es algo que es válido:

$P \to Q$

$\therefore \neg Q \to \neg P$

En otras palabras, si puedes demostrar que en cualquier grafo que no contenga un ciclo hay algún vértice con grado 0 ó 1, habrás demostrado que cualquier grafo en el que todos los vértices tengan grado 2 o superior contendrá un ciclo.