Math 38: Graph Theory Spring 2004
Dartmouth College

Instructor: David Little
Lecture: MWF 12:30-1:35, Bradley 013
X-period: Tu 1:00-1:50, Bradley 013
Office: Bradley 411
Office Hours: MW 3-4, TuTh 11-12
Phone: (603) 646-2960
E-mail:dlittle@dartmouth.edu



General Info/
Announcements

  • 06/03/04 - Solution to Problem 7.1.26
  • 06/02/04 - Homework 8 Solutions (LaTeX Source)
  • 05/26/04 - Homework 7 Solutions (LaTeX Source)
  • 05/19/04 - Homework 6 Solutions (LaTeX Source)
  • 05/17/04 - Exam II Solutions
  • 05/10/04 - Homework 5 Solutions (LaTeX Source)
  • 05/05/04 - Homework 4 Solutions (LaTeX Source)
  • 04/28/04 - Homework 3 Solutions (LaTeX Source)
  • 04/28/04 - Exam I Solutions
  • 04/19/04 - Homework 2 Solutions (LaTeX Source)
  • 04/14/04 - Homework 1 Solutions (LaTeX Source)
  • 04/02/04 - On Writing Proofs
  • 03/29/04 - Graph Theory - Examples and Applications (LaTeX Source)
  • 03/29/04 - Course Syllabus
    * The above files require Adobe's Acrobat Reader.

  • Graph Theory
    Links

  • Graph Theory Open Problems
  • Unsolved Problems - Maintained by Stephen C. Locke
  • Open Problems in Graph Theory and Combinatorics - Maintained by Douglas B. West (Glossary of Terms)
  • Graph Theory Tutorials
  • Graph Theory - from Eric Weisstein's World of Mathematics
  • Graph Theory Resources
  • Graph Theory Lessons

  • Homework
    Due Date Date Assigned Topics Covered Homework*
    -/- 03/29 Introduction: Examples and Applications of Graph Theory Read Chapter 1.1
    04/09 03/31 Basic Definitions and Graph Isomorphisms Read Chapter 1.2
    Problems Chapter 1.1 #10,13,16,21,29,30
    04/02 Walks, Cycles and Bipartite Graphs Read Chapter 1.3
    Problems Chapter 1.2 #2,8,10,17,20,38
    04/05 Components, Cut-edges, Eulerian Graphs Problems Chapter 1.2 #11,27,30
    04/16 04/07 Vertex Degrees and Degree Sequences Read Chapter 1.4
    Problems Chapter 1.3 #1,8,12,14,18,31
    04/09 Directed Graphs Read Chapter 2.1
    Problems Chapter 1.4 #9,15,19
    04/12 Eulerian Digraphs and Trees Read Chapter 2.2
    Problems Chapter 1.4 #26,27
    Problems Chapter 2.1 #2,6,19
    04/23 04/13 Trees and Distance Problems Chapter 2.1 #11,23,27,32
    04/14 Counting Trees and Prüfer Codes Read Chapter 2.3
    Problems Chapter 2.2 #1,7,8
    04/16 Counting Spanning Trees and the Matrix Tree Theorem Problems Chapter 2.2 #12,15
    04/30 04/19 Minimal Spanning Trees and Shortest Paths Read Chapter 3.1
    Problems Chapter 2.3 #2,3,16
    04/21 Matchings Read Chapter 3.2
    Problems Chapter 3.1 #8,10,18,28
    04/23 Hall's Theorem and Coverings Problems Chapter 3.1 #1,5,24 (See Example 3.1.2),26,29
    05/07 04/26 Maximum Matchings Read Chapter 4.3
    Problems Chapter 3.2 #1,5,6
    04/28 Maximum Weighted Matchings
    04/30 Hungarian Algorithm Read Chapter 5.1
    Problems Chapter 4.3 #1,2,3
    05/14 05/03 Network Flow Problems
    05/05 Max-flow Min-cut Theorem Problems Chapter 4.3 #11,13,14
    05/07 Vertex Colorings Read Chapter 5.2
    Problems Chapter 5.1 #1,12,14
    05/21 05/10 Bounds on Chromatic Numbers and Mycielski's Construction Read Chapter 5.3
    Problems Chapter 5.1 #20,31,33
    Problems Chapter 5.2 #1,9
    05/12 Chromatic Polynomials Read Chapter 6.1
    Problems Chapter 5.3 #1,3,5,7,10,11
    05/28 05/17 Chordal Graphs Read Chapter 6.2
    Problems Chapter 5.3 #9,18,19,24
    Problems Chapter 6.1 #2,3
    05/19 Planar Graphs Problems Chapter 6.1 #12,13,21,25
    05/21 Euler's Formula and Kuratowski's Theorem Problems Chapter 6.1 #8,9,33
    -/- 05/24 Five and Four Color Theorems Read Chapter 7.1
    Suggested Problems Chapter 6.2 #1,4,6,12
    05/26 Line Graphs and Chromatic Index Read Chapter 7.2
    Suggested Problems Chapter 7.1 #1,3,5,8,11,12,18,24,26
    05/28 Hamiltonian Cycles Suggested Problems Chapter 7.2 #1,2,3,7,8,10,12,17
    06/02 Unsolved Problems in Graph Theory
    * Reading assignments are to be completed by the next class period.

    LaTeX
    Links

  • A sample LaTeX file which produces the following typeset document once compiled.
  • List Of Mathematical Symbols
  • TeX Reference Card by J. H. Silverman
  • Hypertext Help with LaTeX
  • TeX FAQ
  • Combinatorics.net LaTeX resources
  • The Not So Short Introduction to LaTeX 2e - Tobias Oetiker et. al.
  • Short Math Guide for LaTeX - Michael Downes
  • Download TeX-related software at Comprehensive TeX Archive Network
  • Mac OS related resources can be found at Penn State Mac-TeX
  • MiKTeX - Windows implementation of TeX
  • OzTeX - Mac OS implementation of TeX
  • TeXShop - Mac OS X implementation of TeX