But of course this means that if the equation holds the second term in the sum on the left must also be even. Yet each of the individual terms in this sum is odd, because we said that q was the number of vertices with odd degree. Therefore q must be even. In an graph, the number of vertices with odd degree is even. We have now seen several examples of mathematical proof, and it's time to investigate what they all have in common.
All mammals have hearts All mammals thus far observed have had hearts.
All horses are mammals All horses thus far observed have been mammals. Every horse has a heart. Every horse has a heart. Note that the difference is not the conclusion, but rather the relation between the premises and the conclusion. We now look at a technique of mathematical proof called mathematical induction.