Graph theory provides an excellent example of how abstraction can be used to simplify and solve real world problems. In this course you will prove theorems about graphs, learn to classify graphs by their properties, and discover applications of graph theory such as the traveling salesman problem and the four color theorem.
The schedule below is tentative, and may be subject to change. Changes will be announced in class, and you are responsible for knowing about any changes even if you miss the class when they are announced.
| Week | Dates | Topic | Homework |
|---|---|---|---|
| 1 | Aug 24 - Aug 26 | Introduction | |
| 2 | Aug 29 - Sep 2 | Basic concepts | HW1 |
| 3 | Sep 5 - Sep 9 | Isomorphic graphs | HW2 |
| 4 | Sep 12 - Sep 16 | Bipartite graphs | |
| 5 | Sep 19 - Sep 23 | Bipartite graphs - con'd | HW3 |
| 6 | Sep 26 - Sep 30 | Trees and forests | HW4 |
| 7 | Oct 3 - Oct 7 | Trees and forests - con'd | HW5 |
| 8 | Oct 10 - Oct 14 | Euler paths | HW6 |
| 9 | Oct 19 - Oct 21 | Hamiltonian paths | |
| 10 | Oct 24 - Oct 28 | Hamiltonian paths - con'd | HW7 |
| 11 | Oct 31 - Nov 4 | Planar graphs | HW8 |
| 12 | Nov 7 - Nov 11 | Independence and covering | |
| 13 | Nov 14 - Nov 18 | Independence and covering - con'd | |
| 14 | Nov 21 | Vertex coloring | |
| 15 | Nov 28 - Dec 2 | Vertex coloring - con'd | HW9 |
| 16 | Dec 5 | Review |
Attendance in this class is required. Repeated absences may result in a forced withdrawal from the course. You are responsible for any material you miss due to absence. Please let me know ahead of time if you know that you will not be able to attend class.
The term grade will be based on the following factors.
| Component | Proportion |
|---|---|
| Homework | 60% |
| Quizzes | 20% |
| Final Exam | 20% |
I will assign homework problems every day in class. When the problems are due, I will collect them, but I will also ask you to present some of the solutions in class. Late homework submissions will only be allowed if you present your partial solutions in class! You are allowed to work together on the homework, but your final submissions must be your own work.
Each homework problem will be graded on a simple two point scale:
Your letter grade for homework will be determined by the percent of possible points you have completed. I will use the following scale.
| Letter Grade | F | D | C | B | A |
|---|---|---|---|---|---|
| Score | 0 - 39% | 40 - 54% | 55 - 69% | 70 - 84% | 85 - 100% |
About once a month, there will be a quiz to test your understanding of the material. These quizzes will be announced in advance, and you will know exactly what concepts will be covered on each quiz. You will not be asked to write proofs during the quizzes, instead the quizzes will focus on definitions, concepts and knowledge about graphs. Each quiz will take about 20 minutes.
There will be a cumulative final exam. It will include questions similar to the ones on the quizzes, as well as a few proofs similar to the ones on the homework. A list of potential proof questions will be provided before the exam.
In compliance with the Hampden-Sydney College policy and equal access laws, I am available to discuss appropriate academic accommodations that may be recommended for students with disabilities. Requests for academic accommodations are to be made at the beginning of the semester (except for unusual circumstances) so that appropriate arrangements can be made. Students are required to contact the Office of Academic Success in order to verify their eligibility for appropriate accommodations. How does this look?