General information

Instructor: Sergi Elizalde
Lectures: MWF 10:00-11:15 in Kemeny 120
X-period: Th 12:00-12:50 (won't be used unless otherwise stated)
Office Hours: Tu 9-10:30, Fr 11:05-12:30
Office: Kemeny 332
Email: sergi.elizalde@dartmouth.edu
You are also encouraged to use the Discussions tool to ask questions or comment on other students' questions.

Course description

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).

Textbook

Douglas B. West, Introduction to Graph Theory, Second Edition, Prentice-Hall (available at Wheelock Books).
The home page of the textbook can be found here.

The textbook

Grading

The course grade will be based on the homework (20%), class participation (10%), two midterms (20% each), and a final exam (30%).

Homework

There will be homework due roughly every week. It will consist typically of a reading assignment (of the part of the book covered in class) and some problems. All the homework assignments are posted here. You are encouraged to collaborate on the homework, but what you write has to be your own understanding of how to do the problem. You must state what sources you have consulted, with whom you have collaborated, and from whom you have received help. No late homework will be accepted.

Here you can find some tips on writing proofs . Sketches of homework solutions are posted in the announcements section.

Disabilities and religious observances

Students with disabilities who will be taking this course and may need disability-related classroom accommodations are encouraged to make an appointment to see their instructor as soon as possible. Also, they should stop by the Academic Skills Center in Collis Center to register for support services.
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 before the end of the second week of the term to discuss appropriate accommodations.