General information

Instructor: Sergi Elizalde
Lectures: MWF 12:50-1:55 in Kemeny 006
X-period: Tu 1:20-2:10 (won't be used unless otherwise stated)
Office Hours: M 10:00-11:30, F 1:55-2:55
Office: Kemeny 332
Email: sergi.elizalde@dartmouth.edu
TA help hours: Sundays 7-9 pm in Kemeny 120
You are also encouraged to use the Discussions tool to ask questions or comment on other students' questions.

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

Textbook

Douglas B. West, Introduction to Graph Theory, Second Edition, Prentice-Hall (available at Wheelock Books, and also from other sellers such as Amazon). The book has been placed on reserve at Baker library.
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%).

The midterms are scheduled for Apr 19 and May 10 in class. The final will be a take home exam, handed out on May 26 and due on June 2.

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

You can turn in your assignments either online via canvas (as a scanned file), or on paper by dropping them off in the box labeled "Math 38 (Elizalde)" in the basement of Kemeny Hall. Assignments are due by the beginning of class on Mondays.

The course grader Avery Feingold has volunteered to run weekly help hours on Sundays 7-9pm in Kemeny 120.

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

Honor principle, student accessibility, and religious observances

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

Students with disabilities who may need disability-related academic adjustments and services for this course are encouraged to see me privately as early in the term as possible. Students requiring disability-related academic adjustments and services must consult the Student Accessibility Services office (205 Collis Student Center, 646-9900, Student.Accessibility.Services@Dartmouth.edu). Once SAS has authorized services, students must show the originally signed SAS Services and Consent Form and/or a letter on SAS letterhead to me. As a first step, if you have questions about whether you qualify to receive academic adjustments and services, you should contact the SAS office. All inquiries and discussions will remain confidential.

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.

Graph Theory (SP17)