THE midterm is scheduled for October 23. It will be a closed-book, closed-notes in-class test. It will feature a mixture of short-answer questions (to test your knowledge of the main ideas and definitions) and proofs (to test you theoretical grip on graph theory).
To be prepared, you should have internalized (not just memorized) the following results, and the definitions pertaining to them.
| Chapter 1: | Theorems 1.4, 1.6, 1.8, 1.11, 1.12, 1.14, 1.16, 1.17, 1.18 |
| Chapter 2: | Theorems, corollaries etc: 2.1-2.4, 2.7, 2.10-2.12, 2.19, 2.20, 2.21, 2.22, Kruskal's Algorithm, 2.26, 2.28, 2.29, 2.34, 2.36, 2.37, 2.42 |
| Chapter 3: | Theorems and corollaries: 3.1, 3.2, 3.3, 3.6, 3.7, 3.15, 3.16, 3.22. |
| Chapter 4: | Theorems and corollaries: 4.2, 4.3, 4.4, 4.5, 4.12, 4.13, 4.14, 4.15, 4.16. |
Any ideas encountered in homework problems could appear in the test problems. In addition to the assigned homework, here is a list of suggested problems. (Some midterm questions will be selected from these.)
| Section 1.1: | 2, 3, 5, 6, 7, 8, 11, 13, 14, 15, 16, 17, 20, 22, |
| Section 1.2: | 7, 10, 13 |
| Section 1.3: | 2, 4, 6, 14, 20 |
| Section 2.1: | 2, 5, 6, 8, 11 |
| Section 2.2: | 1, 8, 9, 11, 17 |
| Section 2.3: | 3, 23 (just for Kruskal's alg) |
| Section 2.4: | 1, 2, 5, 9 |
| Section 2.5: | 1, 6, 11 and 14 |
| Section 3.1: | 1, 3, 5, 7, 8, 9, 10 |
| Section 3.2: | 1, 2, 3, 5, 7, 11, 14, 16, 24 |
| Section 4.1: | 2, 3, 4, 6, 8, 14 |
| Section 4.2: | 1, 2, 3, 4, 6, 7, 8, 11, 12, 15, 16, 21, 23, 24 |
For your convenience, here are links to midterms for this class from previous years. Please note that texts differ from year to year, so coverage may vary accordingly. Thus you should use these links only to glean the format and level of our midterm.
| Fall 2011 | [Blank] [Solved] (75 minutes) |
| Fall 2010 | [Blank] [Solved] (50 minutes) |
| Fall 2009 | [Blank] [Solved] (50 minutes) |