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:

• Final Exam

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:

• Information on the Project

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:

• Practice Problems for Quiz 2 (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