Math 322: Graph Theory, Summer Term, 2008.

Relevant course material will be made available on this webpage as the course progresses.

• This term, I will not be following any single textbook. This course will cover significantly different material from what has been normally taught in previous terms.

• I will try to provide free online reference for certain parts of the course. For example, the textbook "Graph Theory With Applications," by Bondy and Murty, is freely available (see below.) About one-third of the course content will come from various chapters in that book.

• Website with complete book as well as separate pdf files with each individual chapter

• In the case that the above website is down or broken, I have the pdf file with the full text on a local drive.

• Course Syllabus in MS Word format.

• Course Syllabus in PDF format.

• Assignment 1 is due Friday July 11th.

• Assignment 2 is due Wednesday July 16th.

• Assignment 3 (handout only) is due Wednesday July 23rd.

• Midterm Review Sheet.

The relevant chapters from the online book are:

• Chapter 1 on general graphs and properties

• Chapter 2 on trees

• Chapter 3 on graph connectivity

• Chapter 4 on Eulerian graphs

• Chapter 5 on graph matchings

A lot of material in those chapters were not covered.... see below "Course Content" as a reminder of what was covered.

• The definition on the Wikipedia article on Graceful Labelings of graphs is poor. The MathWorld article on Graceful Graphs is much more accurate.

• Assignment 4 is due Wednesday August 6th.

• Assignment 5 is due Wednesday August 13th.

• Assignment 6 is not due.

• Horton's counterexample to Tutte's conjecture.

• Final exam schedule. For those who can't view the .pdf or don't want to: the final exam is on Friday, August 15 to be held in CAB 369 starting at 11:30am. The exam will only be two hours long.

• Final exam review sheet.

• The final exam is graded. The median grade on the final exam was 50% and the average was 56%.

• The final grades are calculated. The final average was 68%. Here are the ranges.
• A+ 93-100
• A 87-92
• A- 80-86
• B+ 77-79
• B 72-76
• B- 67-71
• C+ 64-66
• C 61-63
• C- 58-60
• D+ 52-57
• D 46-51
• F 0-45

• The course is over. Why are you still reading?

Course Content

(not including definitions, examples, trivialities, etc)

• Week 1

• Day 1: Introduction; Eulerian graphs

• Day 2: Proof of Euler's Theorem; a graph with minimum degree d has a path of length d; Q: Is it true that any two longest paths in a graph always share a vertex?

• Day 3: Eulerian vs. semi-Eulerian graphs; handshaking lemma; labeled graphs vs. unlabeled graphs; isomorphism; graph complements; self-complementary graphs; Open Problem: do three longest paths in any graph always have one vertex in common to those three paths? (four, five, six paths are also unknown)

• Day 4: The complement of a disconnected graph is connected; special graphs; graphic sequences; Open Problem: does every graph with minimum degree 3 have a cycle whose length is a power of 2?

• Day 5: Graphic sequence algorithm; properties of trees; spanning tree theorems and algorithms (Kruskal's and Prim's)

• Week 2

• Day 6: Cayley's Theorem; Prufer sequences; Graceful labelings; Open Problem: find a closed form expression for the number of unlabeled trees on n vertices; Open Problem: Is every tree graceful?

• Day 7: Graphic sequences revisited (corrections); 2-edge-connected graphs; vertex connectivity < edge connectivity < minimum degree; Menger's theorem (vertex version)

• Day 8: Menger's Theorem (edge version); girth and (r,g)-cages; Fleury's Algorithm; Open Problem: graph reconstruction from single-vertex-deletions.

• Day 9: Assignment #2 and #3 discussions; The maximum matching problem; Berge's Theorem for augmenting paths.

• Day 10: Tutte's theorem; Vertex covers; Koenig's theorem; Regular bipartite graphs; Petersen's theorem; Max flow problems; Open Problem: Seymour's Conjecture on 2nd neighbourhoods.

• Week 3

• Day 11: Ford-Fulkerson algorithm; multi-source, multi-sink flow problems; vertex capacities; the escape problem.

• Day 12: Ford-Fulkerson algorithm; Edmonds-Karp algorithm; single-source and multi-source shortest paths problems; Dijkstra's algorithm.

• Day 13: Dijkstra's algorithm; negative edge weights and the Bellman-Ford algorithm.

• Day 14: DFS and the depth-first search tree; connectivity; cut-vertices; cut-edges; topological sort.

• Day 15: Topological sort; strongly connected components; finding strong orientations.

• Week 4

• Day 16: Euclidean MST; the Gabriel graph; the relative neighbourhood graph; midterm exam review;

• Day 17: Midterm exam.

• Day 18: Midterm back and take-up.

• Day 19: Bipartite matching via max flow; planar and non-planar graphs; Kuratowski's theorem; toroidal embedding.

• Day 20: Plane models; Moebius strip; Euler's formula and inequalities.

• Week 5

• Day 21: A planar graph has a vertex of degree 5 or less; graph colouring; Open Problem: the chromatic number of the square of the 8-dimensional hypercube. Open Problem: the chromatic number of the unit distance graph on the real (2-dimensional) plane.

• Day 22: Genus of surfaces and graphs; toroidal graphs; generalized Euler Formula; maps and the four-colour theorem; Open Problem: the chromatic number of a 2-pire (Earth/moon) map.

• Day 23: Chromatic polynomials and properties; the adjacency matrix; powers of adjacency matrices; counting paths in graphs and digraphs.

• Day 24: Formal languages; deterministic finite automata (DFAs); counting strings and applications to enumeration.

• Week 6

• Day 25: Eigenvalues; spectrum of a graph; trace(A2) = 2|E|; trace(A3) = 6 times the number of triangles; properties of the largest eigenvalue; Hamiltonian graphs.

• Day 26: Hamiltonianicity and counterexamples; Dirac's theorem; Ore's theorem and corollaries.

• Day 27: Solutions to assignment 6.