Skip to main content

Discrete Structures: Course Notes

Mike Janssen

Worksheet 2.1.1 Worksheet
A4US

Guiding Questions.

In this section, we’ll seek to answer the questions:
  • How is mathematical knowledge developed?
  • What is a graph?
  • How can we represent graphs?
Influenced by the ancient mathematician Euclid of Alexandria, mathematical knowledge has traditionally been developed via a careful litany of definition, theorem, and proof. The word definition means more or less what you expect: it is a precise description of the meaning of a term. The mathematical version places an emphasis on clarity and concision. This does not always make the definition of a mathematical term easy to parse, but should make it clear to apply.
A theorem is a true mathematical statement. If you read enough mathematics, you will also see words like proposition, lemma, and corollary. These are all true mathematical statements as well, but have slightly different connotations.
  • A proposition is a true mathematical statement which is not perceived to be important enough to be called a theorem.
  • A lemma is a true mathematical statement which may be somewhat technical to write, but is used to prove a theorem or proposition. One often has the experience of proving a theorem and realizing that a portion of the proof is substantive enough that it can be pulled out and written as the proof of a lemma, to which you can then refer to complete the proof of the theorem.
  • A corollary is a true mathematical statement that follows immediately from the proof of a theorem
     1 
    For instance, suppose you’ve proved that all rectangles in the plane contain only right angles. A corollary to this theorem is that all squares in the plane contain only right angles.
    .
How is the truth of a mathematical statement ascertained? Via proof. One of the goals of this course is develop proficiency writing proofs, and we will explore techniques for doing so in more detail in Chapter 3.
For now, we will focus on the first part of the mathematical litany: definitions. Theorems (and their accompanying proofs) must be about something, so in this section, we introduce one of the basic ideas of the course: the graph.

Problem 2.1.1.

Below there are several examples of objects called graphs. Develop a clear, concise definition of the word graph and explain why each of the objects below meets your definition. For the sake of consistency, we’ll call the circles vertices (or nodes), and the lines connecting them edges.
Figure 2.1.2. A graph.
Figure 2.1.3. A second graph.
Figure 2.1.4. A third graph.
Figure 2.1.5. A fourth graph.
Figure 2.1.6. A fifth graph.
Figure 2.1.7. A sixth graph (no, this is not a mistake).

Problem 2.1.8.

Below there are several examples of objects that are not graphs. If necessary, modify your definition from Problem 2.1.1, and explain why the objects below do not meet your (possibly new) definition —but make sure the objects in Problem 2.1.1 still do!
Figure 2.1.9. Not a graph.
Figure 2.1.10. Not a graph.
Figure 2.1.11. Not a graph.
Figure 2.1.12. (Still) Not a graph.

Definition 2.1.13.

A graph is ....

Activity 2.1.14.

Given the definition of a graph that we’ve come up with, exhibit two additional examples of a graph, as well as two non-examples.
PrevTopNext