Syllabus for MCS-236: Graph Theory (Fall 2011)

Overview

You will learn two things in this course. One is a particular area of mathematics, graph theory. The other is how to participate in mathematics by reading and composing mathematical explanations.

Graph theory is highly applicable. It is the mathematics of social networks, web links, internet routing, biochemical networks, economic markets, the medical residency matching program, deadlock detection, and the allocation of computer storage registers. It also can be appreciated as an area of pure mathematics. It abounds in the kinds of problems that are easy to state, initially puzzling to solve, but then often yield up their secrets in a burst of clarity that leaves you feeling good. At least, I hope it will be that way by the end of the semester, once you've gained some practice.

All of you can and will do mathematics. Most of you will find it at least occasionally frustrating. Temporary frustration when you are actively working on unraveling a puzzle, and it hasn't yet yielded, is fine. But a lot of your frustration won't be of that kind. It will kind that comes from trying to pound in a nail with a screwdriver or slice French bread with a butcher knife. That frustration doesn't mean you are lacking some inherent ability, it just means that we have some work to do together developing your skills so that you'll have the right mental tools for the job. That includes skills at reading mathematics, reasoning about mathematics, and writing mathematics.

Office hours

I will be available in my office (OHS 306) 10:30-11:20 on Mondays, Tuesday, Thursdays, and Fridays, as well as by appointment. Or try your luck: just stop by and see whether my door is open. You may send me electronic mail at max@gustavus.edu or call me at extension 7466. I'll try to put any updates to my office hours on my web page, so check there if in doubt.

World Wide Web

Text

Our textbook is Introduction to Graph Theory by Gary Chartrand and Ping Zhang, McGraw-Hill, 2005. Note that this book is out of print, so you will need to buy a used copy. The Book Mark has acquired what ought to be a sufficient number of copies and other sellers also have used copies.

Reading mathematics

Reading mathematics is not like reading other prose. You need to read it incredibly slowly and actively. Many days I've assigned you only a couple pages of reading, but I'm expecting you to spend hours on those pages, poring over them with pencil and paper at hand, figuring out how the flow of reasoning coheres.

Suppose you are reading instructions for a particular route up a mountain and you come across these lines:

By stepping up and to the right, you will come onto a ledge. On the left, you will see a handhold. From here, a relatively easy climb of 20 more feet leads you to the summit.

Even if you understand every single word in these three sentences, you can't fully appreciate their significance without going to the mountain and trying them out. Presumably there is a connection between the first two, but what is that connection? Maybe the handhold is hidden from view until you step onto the ledge. Then again, maybe it is fully visible, but too high to be practical as a handhold. Is there only one ledge? If not, maybe the author of the instructions intends that you will use sight of the handhold as confirmation that you stepped onto the correct one. More likely, the mention of the handhold is preparation for what implicitly comes next: grasping the handhold. The author is assuming that you can figure out for yourself how to do the "relatively easy climb," presumably starting with the aid of the handhold.

Reading mathematics is like that. Everything connects, but the connections aren't always obvious. Until you do the work of actively engaging in the reasoning and filling in the gaps, you can understand each of the phrases without understanding the larger story they are telling.

Frequently you will read a sentence of the form "Mumbojumbo, therefore, mumble mumble." Each time, you need to ask yourself questions like these:

• Given the prior context, why does the author expect me to believe that mumbojumbo is true?

• Is mumbojumbo in fact true?

• Given the prior context, why does the author expect me to believe that the truth of mumbojumbo implies the truth of mumble mumble?

• Does mumbojumbo actually imply mumble mumble?

• In the broader flow of the reasoning, what role does it play to establish the truth of mumble mumble?

Sometimes the truth of mumbojumbo was established by the immediately preceding sentence. For example, immediately after showing that x is positive, the author might continue with a sentence beginning "Because x > 0, ...." That makes it easy to see narrative flow; at the same time as you see the logical foundation for the new sentence, you see the motivation for the previous one. Other times, the connection may not be quite so close to the surface. For example, the preceding sentence may have established that x is of the form 3k + 7 for some positive integer k. You are expected to plug in the smallest legal value of k, namely 1, and see that x is at least 10, so definitely greater than 0. If you don't do that, you won't be able to catch any mistakes, and mistakes do indeed happen, even in well-regarded textbooks. At least as importantly, you won't be able to understand the narrative flow of how each part of the reasoning connects with other parts; you'll just have a disjointed succession of mumbojumbos and mumble mumbles.

Alternatively, the relevant context for mumbojumbo might not be immediately before it. When you reach the sentence starting with "Because x > 0, ...," you may need to look back through earlier paragraphs to find where this was established. Or perhaps you'll find that it was one of the premises of the theorem; the author is in the midst of proving that something or other is true, provided that x > 0. In that case, you've just discovered why the theorem has that restriction, that is, why the proof wouldn't work if x were left unconstrained.

Finally, there are times when you are expected to figure out that mumbojumbo is true without any help from prior context. If a sentence begins "Because 17 is prime, ...," the author likely hasn't breathed a word about the primality of 17. Instead, you might mentally double check that 17 isn't divisible by 2, 3, or 5.

The logical implications may also require some detective work on your part. Consider the following three examples:

1. Because x > 1, 3x + 7 > 10.

2. Because k > 0, k|S| ≥ 0.

3. Because n > 0, n|U| > 0.

In the first example, you can connect the premise to the conclusion using just your knowledge of how numbers work. In the second example, you need to recognize that the notation |S| represents the number of elements in a set, and that number surely isn't negative. In the third example, you need the same kind of recognition, but you also need to look back earlier in the reasoning, or in the statement of the theorem, to find a place where it was established that the set U is nonempty. You need to train yourself to spot the difference between > and ≥.

Be sure to test boundary cases. Suppose you read a theorem that all graphs of size 3 or more have a certain property. You should see if you can find a graph of size 2 that doesn't have the property. (Otherwise, why was the theorem restricted to the larger graphs?) Also, check a sample graph of size 3 to see that it does have the property. That concrete example will help you understand what the theorem is guaranteeing.

Homework assignments

In the schedule of class topics below, each day with a reading from the textbook will also have a homework assignment indicated. They aren't all there yet, but I promise to have each one in place at least one week before the class. Each one will consist of 1 or 2 exercises. Most commonly these will be exercise numbers from the textbook, but sometimes I will provide a link to a non-textbook exercise.

When I assign two exercises, each one you successfully complete will earn you a grade point. When I only assign one exercise, it will be worth two grade points, and I may credit you with one of the two if you turn in a substantial but not entirely successful attempt.

To receive credit for a one-point homework problem, you must submit your solution within 48 hours of the corresponding class. To receive any credit for a two-point problem, you must earn at least the first point within 48 hours of the corresponding class. Once you have met that threshold, you can continue to work toward the second point up until 120 hours after the class. I suggest that you try to do the homework prior to the corresponding class, without the extra 48 hours, as a way of preparing for class. Also, if you submit homework before the deadline and I indicate that it is not satisfactory, you can still get credit by submitting a revised version up until the deadline.

If either the 48-hour deadline or the 120-hour deadline falls during a weekend or college break, that deadline is extended until the corresponding time on the next day when classes are in session.

This course is a "writing in the discipline" (WRITD) course where I expect you to focus on building your skills at mathematical writing. To ensure you have frequent small opportunities to practice those skills, I will hold even the daily homework assignments to a high standard. Suppose I were to assign an exercise that asked whether there are any integers that are both odd and composite. The following answers would be unacceptable:

• yes

• yes, for example 15

• 15 = 2 ⋅ 7 + 1 = 3 ⋅ 5

An acceptable answer follows:

The integer 15 is both odd and composite. It is odd because it can be written in the form 2k + 1, where k = 7. It is composite because it can be written as the product of two factors, 3 ⋅ 5, neither of which is 1.

I encourage you to submit your homework by email, but I will also accept hardcopy, even a handwritten version that you have neatly copied in pen. Early in the semester, we'll spend a couple days learning to use a text-formatting program called LaTeX that is particularly well suited for mathematical text. From that point on, my suggestion would be that you type your homework in LaTeX and send me both the source file and the resulting PDF file.

Proof portfolio

Over the entire semester, I expect you to write 5 proofs of professional quality. I will provide you feedback on drafts as often as you wish throughout the semester. In some cases I will provide feedback in writing, but often I will invite you to come visit with me to discuss your draft. It is your responsibility to seek that feedback early and often and rewrite your proofs until they meet my quality standard. At the end of the semester, you will earn grade points for each proof that has met my standard; drafts that still need rewriting will not receive partial credit.

Each of your 5 proofs must be of a theorem I deem suitable. I will post a list of suitable theorems on the course web page. This list will grow as we work our way through the course topics. You may also request that I add a particular theorem.

Each of your proofs should explicitly indicate the method (or methods) of proof that it uses, drawing from the following list:

1. direct proof
2. proof by contrapositive
3. proof by contradiction
4. proof by mathematical induction
5. proof by cases

A single proof can use more than one method. In particular, proof by cases will surely be combined with at least one of the others, because each case needs to be proved somehow. (However, you should not count a proof as "by cases" if this only arises as part of proof by mathematical induction, where the base case is distinguished from the inductive case.) You may use the same combination of methods in more than one proof, as long as you cover all 5 methods across your 5 proofs. You will not receive credit for more proofs than you use methods. For example, if you turn in 5 proofs, every one of which uses just a combination of proof by cases and direct proof, then you will only receive credit for 2 proofs, even if all 5 are of high quality.

Tests

There will be two intra-term tests as shown on the schedule below and a final exam as scheduled by the registrar. If you have a conflict with a testing time, please contact me as soon as possible to make an alternative arrangement.

My default assumption is that students will take the test together in our classroom. Therefore, I would ask you to please be respectful and quiet, even after completing your test, so that your fellow students have a good test-taking environment. However, if you prefer to take the test in a separate room, please contact me in advance and I will try to arrange it.

Each of the two intra-term tests will cover material from approximately 1/3 of the course. The final exam will contain a portion testing the remaining 1/3 of the course and another portion reviewing material from the first 2/3.

Exams will be closed-book and mostly closed-notes. You may, however, use a single 8 1/2 by 11 sheet of paper with hand-written notes for reference. (Both sides of the sheet are OK.)

Honor

Students are encouraged to discuss the course, including issues raised by the assignments. However, the solutions to assignments should be individual original work. In your discussions with other students, remember that your primary goal needs to be building your understanding, not just getting the assignment done.

Any substantive contribution to your solution by another person or taken from a publication or online source should be properly acknowledged in writing. Failure to do so is plagiarism and will necessitate disciplinary action.

You are expected to be familiar with the college academic honesty honor code policy and to comply with that policy. If you have any questions about it, please ask.

Grading

You can earn 161 grade points as described in this paragraph, plus additional bonus points for class participation. Each of the 28 days where the schedule shows reading from the textbook, you can earn 2 points from the corresponding homework assignment for a total of 56 points. Another 50 points come from your proof portfolio, namely 10 points for each of 5 proofs. On the tests, you can earn 55 points distributed as follows: 15 points on each of the 2 tests during the semester, 15 more on the portion of the final exam that covers new material, and 10 on the portion of the final that reviews material from the first 2/3 of the course.

Although earning most of these 161 points would be one way to merit a course grade of A, the easier approach would be to supplement your points with bonus points from class participation. You can earn up to one bonus point per class day. I have chosen to adopt San Skulrattanakulchai's standards for what earns a point:

• volunteering in class to write a proof on the board
• asking an interesting question
• having a good idea
• pointing out a mistake in proof that someone makes
• correcting a mistake in proof that someone makes
• helping a fellow classmate understand a point that I seem not to be getting across
• making a perceptive remark

As San says, "I decide which question is interesting, which idea is good, and which remark is perceptive. The mistake in proof can be the one that is made by me, or the authors of the text book, or a fellow classmate, or you yourself. I also decide whether or not your alternate explanation of a point successfully convinces your classmate. I will keep a record of all extra credits you earn throughout the semester and use them in the calculation of your course grade."

I will translate your total number of grade points (including bonus points) into a letter grade as follows:

Please point out any arithmetic or clerical error I make in grading, and I will gladly fix it. You may also request reconsideration if I have been especially unjust.

Accessibility

Gustavus Adolphus College is committed to ensuring the full participation of all students in its programs. If you have a documented disability (or you think you may have a disability of any nature) and, as a result, need reasonable academic accommodation to participate in class, take tests or benefit from the College's services, then you should speak with the Disability Services Coordinator for a confidential discussion of your needs and appropriate plans. Course requirements cannot be waived, but reasonable accommodations may be provided based on disability documentation and course outcomes. Accommodations cannot be made retroactively; therefore, to maximize your academic success at Gustavus, please contact Disability Services as early as possible. Disability Services (https://gustavus.edu/advising/disability/) is located in the Advising and Counseling Center.

Support for English Language Learners (ELL) and multilingual students is available via the College's ELL Support staff person, Andrew Grace (agrace@gustavus.edu or x7395). He can meet individually with students to consult about academic tasks and to help students seek other means of support. In addition, ELL and multilingual students can seek help from peer tutors in the Writing Center. Please let me know if there is any accommodation in the course that would enable you to more fully show your abilities; for example, I would consider allowing extra time on tests, as well as allowing a dictionary in an otherwise closed-book test.

Schedule

Please note that this schedule is my prediction of the pace at which we will be able to move through topics, but reality may differ from this prediction. It is more important that we take full advantage of each topic's learning opportunities than that we cover all the topics. Therefore, if our actual pace differs from the predicted pace, I will issue a revised schedule, even if that requires pruning a topic.

In the reading column, an entry such as A1.1 indicates Section 1 of Appendix 1, A2 indicates the entire Appendix 2, and 1.1 indicates Section 1 in Chapter 1. Sometimes I have indicated an ending page number, such as 3.3–p.70. In those cases, you should read up through the indicated page, though if the page ends with a transitional paragraph (as page 70 does), you needn't concern yourself with it.

*Exercise 3.26 was belatedly turned into a two-point problem, with the second point an extra credit opportunity.

**Exercise 10.18 can be modified by eliminating the word "independent." We skipped the portion of the book where it is defined, and it turns out not to matter for the problem.