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
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
The definition on the Wikipedia article on Graceful Labelings of graphs is poor. The MathWorld article on Graceful Graphs is much more
Assignment 4 is due Wednesday August
Assignment 5 is due Wednesday August
Assignment 6 is not due.
Horton's counterexample to Tutte's
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.
The course is over. Why are you still reading?
(not including definitions, examples, trivialities, etc)
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
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
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.
Day 11: Ford-Fulkerson algorithm; multi-source, multi-sink flow problems; vertex capacities; the escape
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;
Day 15: Topological sort; strongly connected components; finding strong orientations.
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
Day 20: Plane models; Moebius strip; Euler's formula and inequalities.
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.
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.