Course description
MAS 477: Introduction to graph theory
This course is an introduction to some of the major topics of graph theory. They include graph connectivity, matchings, planar graphs, graph coloring, and nowhere-zero flows. Basic notions and theorems covered in Discrete Mathematics (MAS275) will be assumed, but will be quickly reviewed in the first week. It is recommended to take MAS275 before taking this course, unless you are familiar with proofs using the mathematical induction.
Lectures
Time Monday - Wednesday - Friday : 10.00 - 10.50am
Room 309, Building E-11 (Creative Learning Building)
Lecturer Andreas Holmsen
Office hours By appointment
Syllabus
R. Diestel, Graph theory, 4th edition, Springer GTM.
Chapters to be covered:
1. The basics
2. Mathcings
3. Connectivity
4. Planar graphs
5. Colorings
6. Flows
7. Extremal graph theory
9. Ramsey theory for graphs
12. Graph minors
(Certain subsections may be omitted due to time
constraints)
Suggested Problems
Here is a list of suggested problems. These will be reviewed during recitation classes. The list will be updated weekly.
The recitation class will be on Tuesdays, 8.30pm in Room 4415 Building E6-1.
Exams
Here is the final exam
Grading
Midterm (40%), Final (50%), Class participation (10%)
The final grades are distributed as follows
Total score
≥ 90% ⇒ A
≥ 80% ⇒ B
≥ 70% ⇒ C
(Students who do not take the midterm or final exam will
get an F)
Advice
Try to solve the problems in the book. Solve as many as possible, preferably all of them. The best way to master graph theory is by doing as many exercises as possible.