Last modified on

This web page recommends homework (HW) exercises, important dates and the main topics for each exam. The HW lists below are intended to be the minimal required to get by. You should generally do at least 50 per cent more, by choosing similar questions for yourself until you have mastered each section. I intend to give 1 hour exams at the ends of weeks 2 and 4, plus a 2 hr final on the last class day. Each exam covers the recent HW, reading and lectures (but usually not much of the class immediately before the exam), and a few other topics to be listed below, such as textbook proofs. You can print this page if you like, but I will change it as we go along, so check back regularly. I will also announce any major changes in class.

Notice that Exam 1 is scheduled for Friday May 23, to last approx one hour, followed by a shortened lecture. I will provide some study advice in the "Week 2" section asap. I may update these remarks at any time, so check back a few days before each Exam. I usually provide a short list of textbook proofs to learn for each test, but I do not provide sample exam questions [your HW is your best exam preparation]. Also, I will not hold a review, unless we are ahead of schedule. After each exam, I will post the answers and a rough scale on my exam page. Since I have not taught Graph Theory before, I do not have any old exams to post there, but if you search my web site a bit, you can find many of my old exams from other courses, if for example, you want to check out my style.

Week 1: Intro and Connectivity

May 12-16:
Surf this website including the syllabus, my policies, my abbreviations, and perhaps the exam page. If interested, see my grading policies (written for all my classes, not just Graph Theory), but it's not required reading. I sometimes also create "Help" pages including solutions to the harder HW, partial lecture notes, side topics, etc. I have nothing yet for Graph Theory, but let me know if you need anything like that. If you need special treatment (a certified disability, a religious holiday conflict, tech issues, etc) see me ASAP. If there is a good reason why you can't be in class at normal times, bring me a written explanation. 

If you are having any problems, this would be a good time to start visiting me, or sending email questions. If you find an error on this website or make a similar contribution, I may give a little extra credit. Include your name on any email you send me.

Read Chapter 1, with emphasis on terms used at least once in class. Read Ch 2 as we go through it, finishing it by approx Monday May 19. Do enough exercises to master the material. In early Ch 1, that might just mean a firm grasp of the vocabulary. In Ch 2, it also includes understanding the main algorithms and theorems. Here are some recommended exercises for the first 4 lectures (through early week 2). Most of these seem plausible entries for Exam 1. The text has no answer key, but most of these have answers on Prof Ram's site, and you can see me about the rest.

Ch 1 - 1, 4, 6, most of 7, 9, 10, 12, 13, 14, 15, 16, 18, 19, 20, 23, 25, 26, 27, 28, 29, 34, 37, 38, 39
Ch 2 - 1, 4, 5, 6, 7, 8, 10, 11, 21, 25, 26, 28, 29, 30, one of {31, 32, 33}, one of {34, 35, 36, 37}

Here is a (hopefully) corrected proof of Thm 1.5.1 as presented in my May 16 lecture. At least for now, this is the version you should study for Exam 1. I have also answered in this file the question about DFSA and longest paths. I believe the textbook proof of Thm 2.2.2 is also slightly off, but the correction is easy - see my 5/19/14 lecture for that.

Week 2: Trees + Exam 1

May 19-23:
See the updated remarks and HW lists above for Ch 1 and 2.

A student asked about alternative texts for the course. I sometimes refer to Graph Theory texts 1) by Chartrand, 2) by Chartrand and Zhang, 3) by Harris, Hirst and Mossinghoff, or 4) to Discrete Math by Rosen. In my opinion, most of these are well-written, but they do not contain all the topics our text does. If you have your own fave alternative, please tell us.

Exam 1 will be Friday, May 23, the first hour of the class period. It will cover Chs 1 and 2, and the lectures through Monday May 19 (perhaps a bit more TBA). Probably that will include Kruskals Alg and Prims Alg from early Ch 3. Most exam problems may resemble the HW [through approx Ch.3-10], but also study the major algorithms and proofs done in class. Here is a list writtten from May 15, which I may revise early in week 2. The exam may also include True-False or perhaps a definition. Always check this page a few days before each exam for updates. The info here is generally more complete [and accurate] than my remarks in class. Calculators, notes, etc, are not allowed on the exams.

Ch 3 [for Exam 1] - 1, 3, 4, 7, 9, 10
Ch 3 [for Exam 2] - 13ab, 14ab, 15, 16a, 17, 18, 27, 28

Week 3: Networks and Circuits

May 28-30:
Holiday Monday May 26. No class that day !
I often allow Extra Credit projects, if you have an idea you want to pursue, and you check it out with me first (and soon).
We will omit Chs. 4.3-4.6, at least for now, but will look at some variations of FF in class.
If interested, you can read more about networks in most texts on Operations Research.
You can get an alternative (lite?) introduction to Ch.5 topics in a Discrete Math textbook, probably with some easier exercises, if you want.

Ch 4 -1 (FFAlg), 4, 5, 9. You might need to create problems yourself for more practice, or see another text.

Ch 5 - 4 (but not 5.1.3), 10, 11, 12, 13 (do 15 1st?), 15, 19.
Ch 5 - List 2 [maybe harder, longer, or tangential] - 1, 2, 7 (EC?), 16-18.

Week 4: Planarity + Exam 2

June 2 - 6:
NOTE (Tues 6/3/14): Monday's lecture went through the DMP algorithm, which may be on Exam 2. But the exam will not include duality or polyhedral graphs, despite anything I wrote below, or on the review sheet. Here are some additional notes related to Monday's lecture on planarity.

Exam 2 is scheduled for June 6. Here is a review sheet. It will cover Chs 3.3 through 6.3, the parts discussed in class by Monday 6/2/14, or related to the HW through Ch.6.
Rough guide to sections mostly covered - Ch 3.3, 4, 6. Ch.4.1, 2, Ch. 5.1, 2, 6. Ch. 6.1, 2, 3.
Exam 2 will focus more on the assigned HW than Exam I did.
The drop deadline is June 9, I think, but you should confirm this. I hope to return Exam 2 that day. See me if you need advice.

Ch 6 - 1, 7, 8, 9, 10, 11, 12, 15, 16. Note that in #8 you can assume G is maximal planar.
Ch 6 - List 2 - 2, 3, 4, 6, 14. I plan to do #2 in class if time permits, but that problem will not be on Exam 2.

Week 5: Matchings

June 9 - 13:
Suggestion - check online that you are registered for the course, while there is still time to sort out any problems.

Ch 7 - 1, 3, 4, 5, 6, 13. Additional problems for Ch 7.
Also practice with stable marriages. Problems 18-20 seem suitable, but I haven't checked those carefully yet.

Extra credit projects are due by 6/13 unless I give you an extension in writing before that. I do not (yet) have any specific project topics in mind, and leave this to you, but we can talk.

Week 6: Colorings + Final

June 16 - 20:
Ch 8 - 1, 2 (typo), 3, 6, 12 (+justify), 16, 27. Problem 2 should involve "chi_1", not "chi" (colored edges, not vertices).
And (from class):
a) Show that chi(G) is less than or equal to 1 + p -beta(G).
b) If G is bipartite, then chi(G^c)=w(G^c) where G^c is the complement ("G bar").
The Ch 8 supplementary problems on Prof Ram's site are also good practice, though I will not ask you about women-optimal stable marriages.

Try to finish all the HW, at least through Ch 7, by Monday June 16. If you ask about any of these by Monday, I will try to answer them by Wed. Here is an answer to problem Ch.1.25. Also, if you want me to review any particular topics on Wed, let me know by Monday. Complete all business by Wed 6/18, such as bringing in doctors' notes, checking your exam grades, resolving any grading issues, etc.

Final Exam : Friday, 6/20/14, from 2:30pm to 4:45pm [the last class period, the usual time and usual room]. It will cover the entire course, but will emphasize (about 65%) the later topics, not covered by Exams I and II. The final exam counts 40 points, and cannot be dropped; see my policy page about this, about incompletes, etc. Be sure to practice the topics which were weak spots on previous exams, such as the assigned HW problems (ones like these may be over half of the exam). Here is a review page for the final with lists of algorithms and proofs, etc.

I hope you enjoyed the course and learned a lot ! Please let me know if anything special has affected your progress this term, for better or worse.  And please keep in touch. I am always interested to hear how my students fare in their future coursework, etc