General information

Instructor: Sergi Elizalde
Email: sergi.elizalde@dartmouth.edu
Lectures: MWF 8:50-9:55 in Kemeny 108
X-period: Th 9:05-9:55 (used 4 times as indicated in the syllabus)
Office Hours: Tu 10-11, F 10-11:50 in Kemeny 332

Course description

Graphs are used to model pairwise relations between objects, using vertices and edges. The first result in graph theory dates back to 1736, when Euler answered the problem of the seven Bridges of Königsberg. Nowadays graphs are used to model such diverse things as social networks, traffic patterns, and map colorings.

This course will cover the fundamental concepts of graph theory: simple graphs, digraphs, Eulerian and Hamiltonian graphs, trees, matchings, networks, paths and cycles, graph colorings, and planar graphs. Famous problems in graph theory include: the Minimum Connector Problem (building roads at minimum cost), the Marriage Problem (matching men and women into compatible pairs), the Assignment Problem (filling jobs with applicants), the Network Flow Problem (maximizing flow in a network), the Committee Scheduling Problem (using the fewest time slots), the Four Color Problem (coloring maps with four colors so that adjacent regions have different colors), and the Traveling Salesman Problem (visiting a list of cities minimizing the traveled distance).

Le théorème des quatre couleurs sur la carte du monde

Textbook

Douglas B. West, Introduction to Graph Theory, Second Edition, Prentice-Hall.

This book has a home page with additional information, but unfortunately the whole text is not available online. You can buy the book from a local bookstore or from the internet.

A copy of the book has been placed on reserve at Baker library.

The textbook

Assessment

The course grade will be based on four in-class quizzes, a final exam, turning in the weekly homework, and class participation, as follows.

What?	When?	How much?
Weekly homework	Due every Monday	10%
Quiz #1	Wednesday, Apr 12 in class	15%
Quiz #2	Thursday, Apr 27 during X-hour	15%
Quiz #3	Thursday, May 11 during X-hour	15%
Quiz #4	Thursday, May 25 during X-hour	15%
Final exam	Due on May 31st	25%
Class participation	Always	5%

If you will be away on any of the dates that the quizzes are scheduled, please let me know as soon as possible (and well before the quiz date) so that we can make alternative arrangements. The final will be a take home exam, handed out on May 26 and due on May 31.

Homework

There will be homework due every Monday. It will consist typically of a reading assignment (of the part of the book covered in class) and some problems. The homework assignments are posted here. The goal of the homework is for you to practice solving problems similar to the ones that will appear in the quizzes and final exam, so you are strongly encouraged to try to solve the problems on your own. If you get stuck, it is fine to collaborate with other students and exchange ideas, but you are required to write your own understanding of the solution. Also, keep in mind that you won't have outside help for the quizes and the final exam.

You can turn in the homework either online via canvas (as a scanned file), or on paper at the beginning of class on Monday.

We will keep track of whether you turn in the homework and have made a fair attempt to solve the problems, but homework won't be graded. After the homework's due date, the solutions will be posted in the announcements section. You are strongly encouraged to read them, compare them to yours, and ask me about anything that is unclear.

The homework solutions will be posted here each week after the problems are due.

Here you can find some tips on writing proofs.

Honor principle, student accessibility, mental health and religious observances

Remember that Dartmouth's academic honor principle applies to this course.

Students requesting disability-related accommodations and services for this course are required to register with Student Accessibility Services (SAS; Apply for Services webpage; student.accessibility.services@dartmouth.edu; 1-603-646-9900) and to request that an accommodation email be sent to me in advance of the need for an accommodation. Then, students should schedule a follow-up meeting with me to determine relevant details such as what role SAS or its Testing Center may play in accommodation implementation. This process works best for everyone when completed as early in the quarter as possible. If students have questions about whether they are eligible for accommodations or have concerns about the implementation of their accommodations, they should contact the SAS office. All inquiries and discussions will remain confidential.

The academic environment at Dartmouth is challenging, our terms are intensive, and classes are not the only demanding part of your life. There are a number of resources available to you on campus to support your wellness, including your undergraduate dean, Counseling and Human Development, and the Student Wellness Center.

Dartmouth has a deep commitment to support students’ religious observances and diverse faith practices. Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with me as soon as possible—before the end of the second week of the term at the latest—to discuss appropriate course adjustments.