Skip to main content

Discrete Structures: Course Notes

Mike Janssen

Section 3.1 Direct Proof

Guiding Questions.

In this section, we’ll seek to answer the questions:
  • What is a proof?
  • What is a direct proof?
  • What are some ideas for getting started/unstuck when stuck on a proof?
Unlike the natural and social sciences, which largely rely on data, experiment, and statistical analyses, mathematical knowledge proceeds deductively via proof. But what is a proof? We will consider a proof to be a “convincing argument,” written as a short essay, and adhering to the standard rules of mathematical English. But what is an argument? And whom should it convince?
As an illustration, consider a statement of the form “If \(P\text{,}\) then \(Q\text{.}\)” A direct proof will begin with the assumption that statement \(P\) is true. We will use our knowledge of what it means for \(P\) to be true —using other definitions or theorems —to make a new deduction. We continue in this way until we may deduce that \(Q\) is true.
Before an example, we make the following definition.

Definition 3.1.1.

Let \(m\) be an integer.
  • We say that \(m\) is even if there exists an integer \(k\) such that \(m = 2k\text{.}\)
  • We say that \(m\) is odd if there exists an integer \(\ell\) such that \(m = 2\ell + 1\text{.}\)

Activity 3.1.2.

Determine whether the following integers are even or odd by showing that they satisfy the appropriate definition.
  1. 5
  2. 8
  3. 0
  4. 1
  5. \(\displaystyle -57\)
  6. 8,675,309
We now consider the following example proof. For the purposes of this proof and what follows, we may assume that the basic laws of arithemtic of integers are true: an integer times an integer is an integer, an integer plus an integer is an integer, etc.

Proof.

Let \(m\) be an even integer. By Definition 3.1.1, there exists an integer \(k\) such that \(m = 2k\text{.}\) When we square \(m\text{,}\) we obtain \(m^2 = (2k)^2 = 2^2 \cdot k^2 = 4k^2\text{.}\) Observe that we may rewrite \(m^2\) as
\begin{equation*} m^2 = 4k^2 = 2(2k^2). \end{equation*}
Since \(2k^2\) is an integer, we have written \(m^2\) as the product of 2 and an integer. Therefore, \(m^2\) is even.

LaTeX Code 3.1.4.

To typeset an exponent in \(\LaTeX\text{,}\) we use the carat symbol, ^, in math mode. So, m^2 produces \(m^2\text{.}\) If the exponent has more than one character, enclose the expression in the exponent in curly braces; so, m^{n+2} produces \(m^{n+2}\text{.}\)
There are several observations that are worth a moment of our time.

Observations on the Proof of Theorem 3.1.3.

  • The proof begins by restating our assumption: that we are working with a general even integer, \(m\text{.}\)
  • Note that we are not considering a specific even integer, such as 18, and verifying that its square is even. Part of the power of mathematics is that we have tools for proving general statements about all even integers at once. Proofs are not examples, and you shouldn’t treat them as such.
  • The proof is written using complete sentences!
  • The proof takes the reader on a journey, using plural pronouns and active language: “we may rewrite...,” etc.
  • The proof avoids the use of pronouns to refer to a mathematical objects; we don’t square “it”, we square \(m\text{.}\) This keeps things clear and easy to follow.
  • Each step follows from the one before it, though specific reasons are not always cited. Determining when it’s appropriate to cite, say, a definition or theorem by number is a bit of an art form. We’ll figure it out.
  • The proof ends by clearly stating the conclusion we sought.
  • You should consider your audience. If your audience is a group of research mathematicians, you’ll write a far different proof than if you are writing for your classmates. You should write for your classmates.
Prove the following theorems directly.
For the next two theorems, finish the sentence with “even” or “odd,” then prove the theorem.
An axiom is an unproved assumption. Without axioms, we have no starting point for our explorations and deductions. However, since we do not prove our axioms, we should ensure that they are reasonable and clear. We will likely eventually prove Axiom 3.1.9, but for now we may take it as true without proof.
First, a definition.

Definition 3.1.10.

Let \(m,n\) be integers. We say \(m\) and \(n\) are consecutive integers if \(m = n+1\) or \(n = m+1\text{.}\)
Again, in the next two theorems, finish the statement with “even” or “odd”, and prove the theorem.

Question 3.1.13.

Of the theorems so far in this section, which are universally quantified? Which are existentially quantified? Justify your answer.

Subsection 3.1.1 Exploring Graphs

Let’s prove some facts about graphs.

Definition 3.1.14.

Let \(v\) be a vertex in a graph \(G\text{.}\) The degree of \(v\), denoted \(d(v)\text{,}\) is the number of edges incident to \(v\text{.}\) We say a vertex is even if its degree is an even integer, and odd if its degree is an odd integer.

Activity 3.1.15.

Draw at least three examples of graphs. For each graph you draw, count the following:
  • The number of odd vertices.
  • The number of even vertices.
  • The sum of all the vertex degrees.
Make a careful conjecture (that is, an educated guess) about any patterns you observe. Then prove your conjectures.

Definition 3.1.16.

Let \(G\) be a graph. The minimum degree of a vertex in \(G\) is denoted by \(\delta(G)\text{.}\) The maximum degree of a vertex in \(G\) is denoted by \(\Delta(G)\text{.}\)

LaTeX Code 3.1.17.

We typeset \(\delta(G)\) in math mode using \delta(G). Similarly, we typeset \(\Delta(G)\) in math mode using \Delta(G).

Problem 3.1.18.

Let \(G\) be a graph with \(n\) vertices. Determine, with proof, the possible values for \(\delta(G)\) and \(\Delta(G)\text{.}\)

Problem 3.1.19.

Suppose you know that a graph \(G\) has seven vertices, and \(\delta(G) = 3\) and \(\Delta(G) = 5\text{.}\)
  1. Prove that this graph must have at least 12 edges.
  2. Determine, with proof, the largest number of edges possible in this graph.
PrevTopNext