MCS-236: Graph Theory (Fall 2011)

Note: This web site will be modified as the semester progresses.

• General information and schedule
• Non-textbook homework exercises (each in PDF and LaTeX source form)
• Theorems for the proof portfolio
• Notes
  • Another induction example: sum of first n odd numbers equals n². (tex, pdf)
  • Introduction to LaTeX for MCS-236 (tex, pdf)
  • Using TikZ to draw graphs (tex, pdf)
  • More detailed proof of Chartrand and Zhang's Theorem 2.4 (tex, pdf)
  • Isomorphism examples (tex, pdf)
  • Proof from 2011-10-13 (tex, pdf)
  • Proofs from 2011-10-14 (tex, pdf)
  • Minimum spanning trees (tex, pdf)
  • Mathematical writing notes
  • Maximum cut vertices proof (tex, pdf)
  • Informal definition: planar graph (tex, pdf)
  • Some proofs about tournaments (tex, pdf)
  • Some proofs about distances and centers (tex, pdf)
• Notes from last year

  San Skulrattanakulchai prepared these PDF lecture notes for the 2010 offering of this course. I think we will all find them to be a useful reference. He writes that they "are meant to be read, digested, and worked through. When they contain assertions without proofs, you are invited to provide ones. Lots of the proving will be done in class. Some of these handouts are more like worksheets than lecture notes. Omitted details will be filled in in class."

  • Set Theory
  • Logic
  • Relations, Functions, and Sequences
  • Methods of Proof
  • Induction
  • chapter 1: introduction
  • chapter 4: trees
  • chapter 5: connectivity
  • chapter 6: traversability
  • chapter 7: digraphs
  • chapter 10: coloring
• Other links
  • Textbook errata
  • TeX Live and MacTeX distributions
  • LaTeX Wikibook

Instructor: Max Hailperin

Let me know what you think

I would appreciate feedback about the course. I welcome your comments in person or by email to max@gustavus.edu.