MATH 454/MATH 553
Graph Theory and Applications/Discrete Applied Math I
Fall 2011

Instructor: Michael Pelsmajer
office: E1 206, phone: 312-567-5344
office hours: by appointment
email: pelsmajer_(AT)_iit_(DOT)_edu

Syllabus: Chapters 1-7 from Introduction to Graph Theory, 2ed, by D.B.West (Corrections, Typos, Comments and Updates)
Generic Syllabi: Math 454, Math 553 ADA Syllabus Statement


Exam 1: Monday October 17, on material up to and including Section 3.1

Exam 2: TBA

Final Exam: Friday December 9, 2pm-4pm

Class Meetings

1:50pm-3:15pm MW in Engineering 1 room 035

You should attend every class. Before and after material is presented in class, you should read the same material in the textbook.

I strongly recommend that you attend the Collaborative Problem Session each week, which will probably be:

1:50pm-3:15pm F in Engineering 1 room 035 (probably)

Homework problems are assigned on Mondays. By Friday, you should have already worked hard on the problems. Then you will be ready to take advantage of the session, and you will be able to finish by the following Monday, when it is due.

Often there will be Bonus Problems given at Friday sessions, and later posted here. These are worth much less than normal homework problems. I am not so concerned about the quality of writing, just the answers. I may give extra bonus for clever/nice ideas. I will collect them on Wednesday.

What is Expected of Students

What is a... Simple Graph? Path? Trail? Perfect Matching? Etc. Graph Theory has many definitions and examples that you will not have seen in other classes, and you need to make them your "friends", to be as comfortable with them and their basic properties as you are with Sin(x), pi, and continuity.

Theorems Not just the statements, but being able to perform straightforward applications, and recognizing situations where the theorem can be applied.

Solving Challenging Problems using "techniques" such as

Write Clear, Complete Explanations (Proofs)

The Difference Between Math 454 and Math 553

Math 454 students can skip one homework problem in each assignment.
Math 553 students each have to do a project, eventually giving a talk. (More about this later.) Exam and homework scores are interpreted differently.


Students are encouraged to discuss problems together, but solutions must be written up individually.

Here are some additional problems, for those of you that want more practice and/or more of a challenge:

Bonus problems:

Overall Grading Policy

Homework 40%, two exams and a final exam 20% each
October 31 announcement: If you do a project, it will be factored in, worth 10-15% of the overall grade

Projects (announced October 31 by email)

I would like to revise the syllabus to make the projects optional for everyone, including 454 students. However, if I don't approve your project plan, then you cannot do it, and your grade will be determined entirely from homeworks and exams. (Which is fine. I think that the homeworks are the main part of the course, so I am happy when someone chooses to put all their effort there. But I also like nice projects.)

Grading: Worth 10-15% of the overall grade, if you decide to do a project. A good project could raise your grade, and a bad project could lower your grade.

Each project will have at most 2 people.

There must be some kind of presentation, and if there are 2 people, both must share the job equally.

It must involve graph theory in a substantial way.

It must be new to you (for those of you who have seen graph theory elsewhere).

Possible topics:

Let me know if there are any objections. And if you are thinking about doing a project, talk to me about it ASAP so that we can agree on what it will consist of.

Advice, Tips

Not yet.

ADA Syllabus Statement

Reasonable accommodations will be made for students with documented disabilities. In order to receive accommodations, students must obtain a letter of accommodation from the Center for Disability Resources and make an appointment to speak with me [the instructor] as soon as possible. The Center for Disability Resources (CDR) is located in Life Sciences Room 252, telephone 312-567-5744 or