Concept of proof by contradiction

68 Views Asked by At

I should proof this by contradiction:

A graph $G$ has vertices of which all have degree of at least $2$. Prove that $G$ contains a cycle.

So I thought: Prove: if a graph $G$ has vertices all of which has degree $0$ or $1$, then it has a cycle?

Then when I can't get a cycle it will prove the original statement? But that doesn't sound like a prove.

1

There are 1 best solutions below

0
On BEST ANSWER

That is indeed not a proof. Just because you are able to show that a graph where all vertices have a degree of 0 and 1 does not have a cycle does not imply that every graph where all vertices have a degree of 2 or higher must have a cycle. You are basically making the logical fallacy of Denying the Antecedent:

$P \to Q$

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

This is not a valid inference: Suppose that I am happy if I win the lottery ... Does that mean that I am not happy when I don't win the lottery? No.

And by the way, the negation of all vertices having degree of 2 or higher is not that all vertices have degree 0 or 1. The negation would be that there is some vertex with a degree of 0 or 1.

Now here is something that is valid:

$P \to Q$

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

In other words, if you can show that in any graph that does not contain a cycle there is some vertex with a degree of 0 or 1, then you will have shown that any graph where all the vertices have degree 2 or higher will contain a cycle.