News

Final exam: regular time for MWF10 courses, which, alas, is 8am Saturday morning June 1, in our usual classroom.

Abstract

A graph is nothing more than a collection of points (called "vertices") some pairs of which are connected by lines (called "edges"). The simplicity of the definition means that graphs are ubiquitous as models, used for the world-wide web, biological systems, transportation networks, economic markets and countless other applications. Nonetheless, graph theory underlies important concepts and sometimes deep theorems of mathematics.

Because the raw material of graph theory is so elementary, the subject is, in addition to its intrinsic interest, a great canvas upon which to learn the whole process of mathematics: experiment, conjecture, proof. In particular, if you've always been uncomfortable with proofs---unsure when an argument constitutes a proof, and/or clueless about how to construct one---this is a great place to turn your weakness into a strength.

Prerequisites: Basic linear algebra (Math 22) or permission of the instructor.

Here is a (tentative) rough weekly syllabus. Note that for the most part it matches the progression of chapters in the text.

1. What is a graph? Examples, generalizations, applications

2. Trees and graph distance

3. Matchings and the marriage theorem

4. Connectivity and components

5. Graph coloring

6. Planarity and embedding

7. Matroids and perfect graphs

8. Ramsey theory

9. Random graphs

Classes

Room: Kemeny Hall 004
Lectures: "10" slot, in particular: Monday, Wednesday and Friday 10-11:05.
X-hour: Thursdays (same room) 12:00 pm--12:50pm.

Staff

Instructor:

Peter Winkler -- Kemeny Hall 231 / Tel. 6-3468
Office Hours: M 2:30-3:30; W 1:30-2:30; F 2:00-3:00.

Textbooks

Douglas B. West, Introduction to Graph Theory, Second Edition, Prentice-Hall.
Text home page here.

Grading

Your grade will be based on homework (20%), class participation (10%), two in-class exams (15% each) and final exam (40%).

Homework

Homework will be assigned at each class period, due at the beginning of the next class.

Assignments

Due Wednesday March 27: 1.1.1, 1.1.2, 1.1.4

Due Friday March 29: 1.1.10, 1.1.11; and if you can, try 1.1.22.

Due Monday April 1: 1.1.14, 1.1.27(hard). And try to find the smallest rigid graph with more than one vertex (recall that "rigid" means that there is only one automorphism).

Due Wednesday April 3: Read 1.2, and do 1.2.1, 1.2.3. Also: if M is the adjacency matrix of the graph G, what interpretation can you give to the u,v entry of the matrix you get by raising M to the kth power?

Due Friday April 5: 1.2.11, 1.2.22.

Due Monday April 8: 1.3.1, 1.3.7, 1.3.14

Due Wednesday April 10: Compute the number of isomorphism types of graphs of order 5, and for each type, the number of labeled examples.

Due Friday April 12: 1.3.8, 1.3.17, 1.3.20.

Due Friday April 19: 2.2.1, 2.2.5, 2.2.7.

Due Monday April 22: 2.2.20

Due Thursday April 25: (1) Show that every path is graceful; (2) Find all graphs on 6 vertices whose vertices can be mapped to the plane in such a way that two vertices are adjacent iff they are at distance one, and such that every three vertices contain at least one edge. Alternatively: prove that there is only one graph with this property that has 7 vertices.

Due Friday April 26: Prove that repeatedly removing the most expensive edge that doesn't disconnect your graph results in a minimum-cost spanning tree.

Due Monday April 29: Prove that any 2m-regular graph can be decomposed into m-edge stars.

Due Wednesday May 1: Count perfect matchings in (a) the cube; (b) the Petersen graph.

Due Friday May 3: (1) Prove or disprove: a tree can have at most one perfect matching. (2) Prove Konig's Theorem (that the edge-coloring number of a bipartite graph is equal to its maximum degree) using the Lemma proved in class.

Due Wednesday May 8: State and prove the TONCAS for decomposition of the edges of a graph into copies of a two-edge path.

Due Friday May 10: Prove that if all edges of a (connected) graph are of different lengths, then there is a unique minimum-cost spanning tree.

Due Monday May 13: (a) Get an upper bound on the number of rounds the proposal algorithm can take, when finding a stable matching between n men and n women. (b) Suppose there are 3 men, a, b and c, and 3 women, d, e, and f. Preference lists are: for a, def; for b, efd; for c, fde; for d, bca; for e, cab; and for f, abc. What matching do you get from the proposal algorithm? What matching do you get if the women do the proposing? Are there any other stable matchings possible here?

Due Wednesday May 15: Apply the Ford-Fulkerson augmenting path algorithm to a network of your choice, and find a minimum cut to make sure you're finished.

Due Friday May 17: Use the Max-Flow/Min Cut Theorem to prove the maximum matching TONCAS for bipartite graphs. (For Matt Jin and Feynman Liang: find a network on which the Ford-Fulkerson algorithm may fail to terminate.)

Due Monday May 20: (a) Prove that the box product of graphs G and H can be colored with k colors, where k is the maximum of the chromatic numbers of G and H. (b) Play around and try to guess the relationship between the chromatic number of the "X"-product and the chromatic numbers of its factors.

Due Wednesday May 22: Prove that every planar graph has a vertex of degree at most 5.

Due Friday May 24: Use Kuratowski's Theorem to prove that the Petersen graph is not planar.

Due Wednesday May 29: Prove that every graph on 6 vertices contains either a triangle (three vertices with all included edges), or three vertices with no included edges. (Or both.)

Honor Code

Students are encouraged to work together to do homework problems. What is important is a student's eventual understanding of homework problems, and not how that is achieved. The honor principle applies to homework in the following way. What a student turns in as a written homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. Students are discouraged from using solutions to problems that may be posted on the web, and as just stated, must reference them if they use them. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code.

If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me, and I will be glad to help clarify things. It is always easier to ask beforehand than to have trouble later!

Disabilities

I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations with me, which might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate.

The Student Disabilities Center is located at 318 Wilson Hall, ext. 6-9900, http://www.dartmouth.edu/~accessibility, if you have any questions. Any student with a documented disability requiring academic adjustments or accommodations is requested to speak with me by the end of the second week of the term. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability and advise on an appropriate response to the need. It is important, however, that you talk to me soon, so that I can make whatever arrangements might be needed in a timely fashion.