We begin our last major unit of the course with this class, namely the concept of a tree. A tree is a connected graph with no cycles and no loops – so when you draw it, it literally looks like a real tree. Trees are the Swiss Army Knife of computing and mathematics, so useful that you will find them seemingly everywhere we have to count or keep track of complex arrangements. In this class we will define what a tree is and look at examples and non-examples of trees; and our main focus of class is to prove an important Theorem (10.1.2) that characterizes the behavior of trees.
Basic objectives: Each student is responsible for gaining proficiency with each of these tasks prior to engaging in class discussions, through the use of the learning resources (below) and through the working of exercises (also below). Note that important new terminology is given in italics.
- Determine whether a graph is or is not a tree.
- Explain the meaning of Theorem 10.1.1 and apply the result.
- State Theorem 10.1.2 and outline its structure (especially what it means to say "the following are all equivalent").
- Apply the results of Theorem 10.1.2 to derive information about trees.
Advanced objectives: The following objectives are the subject of class discussion and further work; they should be mastered by each student during and following class discussions.
- Sketch an outline of the proof for Theorem 10.1.2.
Reading: Read Section 10.1 of your textbook.
Video: None this time.
The following exercises are to be done during and following your reading and viewing of the resources. Work these out on paper and then enter the responses into the appropriate submission form (see Submission Instructions) by the deadline. You will receive a mark of Pass if each item response shows a good-faith effort to be right and is submitted prior to the deadline.
- One of the Theorems in this section you’re asked to focus on, Theorem 10.1.2 gives five statements and says “The following are all equivalent”. What does that mean?
- A graph has 32 vertices and 25 edges. Is it possible that this graph is a tree? Explain in one sentence.
- In your own words, why is Theorem 10.1.1 true? Explain what is going on in the proof of this theorem, in a way that a high school student could easily understand (i.e. don't be overly technical and use a lot of notation).
Submit your responses using the form at this link: http://bit.ly/1Rz9rzv