A very useful question to ask yourself when you are trying to figure out if something is true or not is, "What if this wasn't true? This kind of thinking is at the heart of a proof by contradiction.
These are the steps in a proof by contradiction:
State the opposite of what you are trying to prove.
For the sake of argument, assume that this (the opposite) is true.
Beginning with that assumption, see what conclusions you can draw. These conclusions will be based only on the assumption you made, and things that are true
Try to draw a conclusion that you know is false or that contradicts something that is true.
If you can draw a false conclusion from the assumption and other true statements, you know that the assumption must be false.
But the assumption is the opposite of what you are trying to prove. If that is false, what you are trying to prove must be true. And so you have proved it.
An Example of Proof by Contradition
You can use a proof by contradiction to show that a solution to the Three for the Money problem, it will be a graph that has an even number of vertices.
It doesn't matter how many vertices there actually are, only that the number is odd. Let p stand for the size of the graph.
Since the graph is 3-regular, the degree of every vertex is 3. Therefore, the sum of the degrees of all the vertices is 3 times p, or 3p.
Because p is an odd number, 3p will always be odd.
We know from the First Theorem of Graph Theory that the sum of all the degrees of all the vertices is twice the number of edges. No matter how many edges there are, that number will always be even.
We have just concluded that if a 3-regular, planar graph of diameter 3 and an odd number of vertices exists, the sum of the degrees of all the vertices will be a number that is both odd and even!
Therefore, such a graph cannot exist.
We do not arrive at the same contradiction if the graph has an even number of vertices. Therefore, if a graph exists which meets the conditions of the Three for the Money problem it will have an even number of vertices.
