Graph Theory Bard College

## Graph Theory

• Professor: Maria Belk
• Office: The Learning Commons, Stone Row basement
• Email: mbelk@bard.edu
• Class schedule: Monday 3:10–4:30pm in RKC 111
• Textbook: Introduction to Graph Theory, 4th Edition or 5th Edition, by Robin J. Wilson
• Office Hours:
• Tuesday 12–1pm in the Learning Commons
• Wednesday 1:30 –2:30pm in the Learning Commons
• Thursday 6:10–8:10pm in RKC 101

## Announcements

The takehome final is due on Friday, December 19 by 5pm. Here is a link:

Projects: The final project for this course involves giving a talk on a topic related to Graph Theory. You can work in groups of 2 or 3 people, or you can work by yourself. The following page contains a list of possible project topics:

The second quiz is in class on Wednesday, November 19. It covers coloring graphs, Markov chains, and Max Flow/Min Cut. Here are links to Practice Problems and Answers:

## Course Requirements

• Homework: There will be weekly homework assignments. I encourage you to work with others on the homework assignments; mathematics is generally easier and more enjoyable when working with others. You should write up your own solutions independently and acknowledge all collaborators.
• Quizzes: There will be a couple in-class quizzes. Quizzes will be announced in advance.
• Exams: There will be two exams: a take-home Midterm and a take-home Final.
• Project: There will be one project consisting of a class presentation. You can work on the project indivdually or in pairs. More details about the project will be given later in the semester.

Your grade will be based on homework assignments (30%), quizzes (10%), two exams (40%), and a project (20%).

## Assignments and Tentative Syllabus

 Week Dates Topics Readings Homework Week 1 Sept. 1, 3 Introduction to Graphs, Instant Insanity, Eulerian graphs 4th Edition: Sections 1–6 5th Edition: 1.1–1.4, 2.1–2.2 Homework 1 Week 2 Sept. 8, 10 Eulerian Graphs, Hamiltonian Graphs 4th Edition: Sections 7–8 5th Edition: 2.3–2.4 Homework 2 Week 3 Sept. 15, 17 Algorithms, Trees 4th Edition: Sections 9–11 5th Edition: 3.1–3.3 Homework 3 Week 4 Sept. 22, 24 Algorithms Homework 4 Week 5 Sept. 29, Oct. 1 Planar Graphs 4th Edition: Sections 12–13 5th Edition: 4.1–4.2 Homework 5 Week 6 Oct. 6, 8 Graphs on Other Surfaces, Quiz 1 4th Edition: Sections 14–16 5th Edition: 4.3–4.4 Practice Problems for Quiz 1 (and Answers) Week 7 Oct. 15 Graph Minor Theorem, Coloring Graphs 4th Edition: Section 17 5th Edition: 5.1 Homework 6 Week 8 Oct. 20, 22 Coloring Graphs 4th Edition: Sections 18–21 5th Edition: 5.2–5.5 Homework 7 Week 9 Oct. 27, 29 Chromatic Polynomial 4th Edition: Section 21 5th Edition: 5.2 Midterm Exam Week 10 Nov. 3, 5 Markov Chains 4th Edition: Sections 22–24 Homework 8 Week 11 Nov. 12, 14 Network Flows 4th Edition: Section 29 5th Edition: 6.3 Homework 9 Week 12 Nov. 17, 19 Menger's Theorem 4th Edition: Section 25, 27–28 5th Edition: 6.1–6.2 Practice Problems for Quiz 2 (and Answers) Week 13 Nov. 24 Matchings 4th Edition: Sections 30–33 5th Edition: 7.1–7.2 Week 14 Dec. 1, 3 Matroids 4th Edition: Sections 30–33 5th Edition: 7.1–7.2 Homework 10 Week 15 Dec. 8 Matroids Week 16 Dec. 15, 17 Presentations