Let me leave you with a bit of commentary on the first of the Reading Questions at the end of the section.

Is there more than one graph with 5 vertices and 6 edges?

When working with graphs, we need to understand what it means to be a graph. The definition of graph is:

An ordered pair G = (V, E) consisting of a nonempty set V (called the vertices) and a set E (called the edges) of two-element subsets of V.

Graphs are equal when V and E are equal, but when we talk about more than one graph we are interested in the concept of isomorphism:

An isomorphism between two graphs G1 and G2 is a bijection f: V1 -> V2 between the vertices of the graphs such that {a, b} is an edge in G1 if and only if {f(a), f(b)} is an edge in G2.

I want to draw your attention to the fact that isomorphism is an equivalence relation, which means it is reflexive, symetric, and transitive. When we ask if two graphs are the same, we are usually asking if they are isometric.

In this first reading question, we are really asking is: Is there more than one isomorphism class with 5 vertices and 6 edges?

Take a look at this:

Well, what do you think?

Select one of you to send me an email telling me how you divided up the Additional Problems from Section 2.1: Problems and Definitions for presentation in class on Tuesday.

Use the rest of class time to find solutions to as many of these as time permits, beginning, naturally, with the one you selected.

We will have a test today on Chapter 1: Logic and Proofs.

Read section 2.1: Graph Theory: Problems and Definitions. Spend some time thinking about the famous Seven Bridges of Königsberg problem presented at the beginning of the chapter.

We'll begin class by discussing any questions you have from Section 1.5: Proofs about Discrete Structures. In the previous sections we learned about the process of doing formal proofs using the rules of logic, but our goal to use proofs to better understand the discrete mathematical structures that are object of our study. To meet that goal as our textbook author states, requires an understanding of the mathematical objects and structures the proofs are about. That means becoming comfortable with the definitions of these mathematical objects, and developing an intuition about how they behave. Again, to quote our textbook author:

Why are we writing proofs? Besides practice in becoming better reasoners, diving into careful proofs about discrete structures is a way to learn more about the structures themselves. They are a playground for exploring mathematics, to help us build intuition for mathematical structures. So we study structures to help us write proofs about them, and we write proofs about them to help understand the structures. Bootstrapping!

After discussing this section and the exercises assigned last Thursday. You'll have the rest of class and homework time to continue working exercises from the lists below.

Prepare a single sheet of 8 1/2 by 11 inch paper, front and back, with notes you can use on Wednesday's test. I recommend you include the definitions and propositions presented in the chapter.

Here is a list to focus on for the test on Wednesday:

Section 1.5: Proofs about Discrete Structues

• Practice Problems: 1 through 5
• Additional Exercises: 1 through 12

Section 1.6: Chapter Summary

• Chapter Review: 1 through 7, 8a, 9 and 10

Be sure you are comfortable generating truth tables, and can do the kinds of proofs presented in the examples and exercises, which means being able to use the definitions and propositions effectively. Having these handy on your 8 1/2 by 11 inch resource sheet will be most useful to you.