``Doing'' proofs often strikes fear into the heart of the non-mathematician, probably because they are associated with the dense, almost incomprehensible language packed with strange symbols and Greek letters that characterizes the proofs in a math book.

It is true that experienced mathematicians communicate the proofs of their theorems in a sparse language that wastes no ink on the page. Inexperienced mathematicians should remember that when they are communicating with one another, completeness, comprehensibility, and understanding are far more important than dense language. What matters the most is showing that the proof has been pursued logically, and that there are no leaps or gaps in the path to the conclusion.

Always in mathematics, it is important to ask, ``How do I know this?'' and ``Am I sure that this is true?'' and to communicate the answers to those questions in language that is clear in the mathematical community to which you belong.

It is important to remember that proof is not persuasion. Something is not proved mathematically because it seems believable. A statement is true mathematically when, by the rules of logic, it is irrefutable.

Understanding the three proof techniques of induction, deduction, and proof by contradiction can often give you ideas for approaches to take when you are struggling with a problem. You can think of these three techniques as patterns of reasoning. These patterns of reasoning are useful in two ways:

· Understanding them can help you follow someone else's reasoning better when you know what technique they are using.

· When you have made a conjecture and you want to try to prove that it is true, experimenting with the different proof techniques might help you find a proof.

Two other techniques, proof by typesetting and proof by intimidation are often used by the unscrupulous. Don't be fooled!

Statements, Conjectures, and Theorems

In mathematics a statement or assertion is a sentence that you are trying to evaluate as true or false. A statement wouldn't have words in it like maybe, perhaps, or sometimes. When you make a statement, you try to make it as precise as possible.

When you think that a statement that you have made is true, you call it a conjecture.

When you have proved that the statement is true, it is called a theorem.

The Rules of Logic

The rules of logic are based very much on the way that we think and draw conclusions about the world around us. This makes them hard to analyze sometimes because we think without thinking about how to think!

One way to see how those rules work for us, though is to see what happens when we break them.

The rules of logic are applied carefully in proofs that use the techniques of deduction, induction, and proof by contradiction

Deduction

We use deductive reasoning when we begin with things that we know are true, put them together, and follow them to the conclusions to which they lead.

The First Theorem of Graph Theory is also an example of a deductive proof.

What this all means:

This is a theorem which relates the number of edges in a graph to the degree of the vertices.

It is actually a very simple statement that just looks complicated because of the notation. The idea is this:

Recall that the degree of a vertex is the number of lines that end at that vertex.

How many line-endings will there be in the whole graph?

Well, two for every line, of course! One on each end!