Course Description
-- GRAPH THEORY - Math 423 -- Spring 2010Instructor: Louis H. Kauffman
Office: 533 SEO
Phone: (312) 996-3066
E-mail: kauffman@uic.edu
Web page: http://www.math.uic.edu/~kauffman
Text Book: "Graph Theory with Applications" by Bondy and Murty
Graph Theory MCS-423 meets at 10AM in Adams Hall 302 on MWF in the Spring Term of 2010. Math 215 is a sufficient prerequisite for the course. The course covers basic concepts of graph theory including Eulerian and Hamiltonian cycles, trees, colorings, connectivity, shortest paths, minimum spanning trees, network flows, bipartite matching, planar graphs. We will also look at a bit of graph theoretic topology and knot theory. See Bondy and Murty. The book "Graph Theory with Applications" by Bondy and Murty will be used for the course. The book is freely available on the web at the above link.
There will be one hour exam, one problem set and one final exam. Homework is collected each week and graded. Your homework record will help in deciding your final grade in the course.
Keep watching this webpage for problems and notes related to the course.
See ASSIGNMENTS. This is a list of all problems assigned in the SPRING 2010 course.
See Problem Set. This Problem Set is due on April 30, 2010.
See Solutions. Solutions to the above problem set.
See Class Notes #2. Class Notes relevant to the above Problem Set. Euler Formulas for Surfaces both orientable and non-orientable. (In the exercise about surfaces, I meant to write "S = Surface depicted with a disk glued to the boundary." Please solve with that in mind.)Penrose coloring formula.
FINAL EXAM - Friday, May 7, 2010. FROM 10:30AM to 12:30AM in Adams Hall, Room 302.
See Final Exam. The final exam.
See Final Solutions. Solutions to the final exam. There is a misprint on page 5. The recursion relation should be A^(k+4) = 5 A^(k+2) + 4 A^(k+1), and similarly with the indices.
WARNING: In Exercise 2.4.2, the suggestion in the book on page 228 is WRONG! The correct recursion formula is W(n+1) = 4(W(n) - W(n-1)) + W(n-2). The sequence starts: 1, 5, 16, 45, 121, 320, 841, 2205, 5776, 15125, 39601, 103680, 271441, 710645,... You may enjoy looking this up in the Online Encyclopedia of Integer Sequences. Note that you are still responsible for organizing your own recursive procedure for this problem.
See Color Theorems. This is a survey article about coloring theorems, including a sketch of the computer approach to the four color theorem. The article is from a now out of print magazine called "Manifold".
See Surfaces. The Wikipedia entry on surfaces. In this, please also look at the link to "Conway's Zip Proof" of the classification of surfaces.
See Cayley Graphs. A Chapter from the book "Contemporary Abstract Algebra" by Joseph Gallian about the Cayley Digraphs of Groups.
See Crossing Number. Webnotes about the crossing number of a graph. Useful for the homework due March 31.
See Class Notes #1. Class Notes for Week of February 1- 5, 2010.
See Diagrammatic Matrix Algebra for notes on matrix algebra and diagrams. This file will modified during the course.
See Linear Equations and Feedback for notes on diagramming systems of linear equations as systems with feedback associated with an input-output graph (Mason's Rule for Linear Systems).
See Electrical Graphs for an exposition of how to solve for conductance in a graphical network, and then see Matrix Tree Theorem for a proof that the Kirchoff matrix enumerates spanning trees in a graph. For more about electrical graphs and topology of knots and links see Electrical Knots for a graphical approach to knots that relates topology to conductance. See Wang Algebra for a clever approach to graphs and spanning trees. See Wang Algebra Progam for a Mathematica program that calculates the spanning trees in a graph via the Wang algebra. See Electricity for an exposition by Duffin of the application of Wang algegra to the calculation of electrical conductance. See Duffin for Duffin's long and intetersting article on this subject.
See KELLEY Excerpt on basic mathematics from book by John Kelley, part of the telvision course "Continental Classroon" that Kelley gave in 1960. This excerpt is useful for reviewing basics about numbers, the concept of a group and the basics of set theory.
See Konigsberg Bridges. This is a link to a website about the Konigsberg Bridge problem and Euler's work.
See Group Theory. This is a link to the Wikipedia entry on group theory.
See AutWiki and AutWolfram. These are links to information about automorphisms of graphs.
See Matrix Algebra. This is a link to an article on the history of matrix algebra that ends with a concise introduction to matrices.
See Adjoint Matrix. This is a link to the Wikipedia entry on Adjoint Matrix and the formula for matrix inverses.
See EigenValues. This is a link to the Wikipedia entry on eigenvalues.
See GoodWill Hunting. This is a link to a webpage devoted to a graph theory problem that was in the movie "Good Will Hunting".