Math 38: Graph Theory

• Instructor: Rebecca Weber
       Office hours (in 317 Kemeny) Tu 12:45-1:45, We 2-3, Th 2:30-3:30 and by appointment.
• Graduate Assistant: Amir Barghi
       Office hours (in 216 Kemeny) We 1:30-2:30, Th 2:00-3:00 and by appointment.
• Class meets MWF 10:00-11:05, X-hour Th 12:00-12:50 (will be used), Kemeny 004
• Textbook: Introduction to Graph Theory (2nd Edition) by Douglas B. West (available at Wheelock Books)
       We will cover chapters 1 and 2, sections 3.1, 4.1-2 and 6.1-2, and selections from chapters 5, 7, and 8.

Dates and Topics (to be augmented as we go along)

• Week 1 (Mar 28-Apr 1): no x-hour
  • basic graph definitions and properties, trees (M 1.1 to p 6, 1.1.20, 1.1.35-36; W 1.1 loose ends, 1.2; F 2.1 to p 69)
  • Quiz Practice: 1.1 (p 14) #1, 4, 5, 11, 13, 18; 1.2 (p 31) #1, 2, 14, 15, 20, 22, 40
• Week 2 (Apr 4-8):
  • spanning trees: enumeration and optimizing; shortest paths (M 2.1 to p 70, 2.2 to p 82; W 2.2 to p 85 and 87-88; F finish 2.2 87-88, 2.3 to p 98)
  • Quiz Practice: 2.1 (p 75) #2-5, 7, 8, 17-19, 22, 24, 26, 31-33, 39, 40; 2.2 (p 92) #1, 4, 7, 8, 10, 13, 20
  • x-hour: graph coloring (5.1.1-7, 5.1.12-14, 5.1.22)
• Week 3 (Apr 11-15): Amir's office hours canceled on Wednesday (4/13).
  • rest of spanning trees and shortest paths; matrices in graph theory; matchings (M rest of 2.3 to p 98, 1.1 p 6-7; W 1.1 p 6-7, 2.2 p 85-87, start 3.1; F 3.1)
  • Quiz Practice: 2.3 (p 103) #2, 4, 10; 1.1 (p 14) #2, 3, 30; 1.2 (p 31) #30
  • x-hour: graph coloring (5.1)
• Week 4 (Apr 18-22)
  • rest of matchings; cuts and connectivity; k-connectivity (M/W rest of 3.1 to p 115; W/F 4.1)
  • Quiz Practice: 3.1 (p 118) #1-11, 13, 18, 21, 22, 43; 5.1 (p 199) #2, 4, 7, 12, 14, 18
  • x-hour: Hamiltonian paths (7.2.1-5, 7.2.7-9)
• Week 5 (Apr 25-29): All Wednesday office hours canceled (4/27); Rebecca has additional office hours Thursday 4-5; exam Friday Apr 29 in class         review sheet
  • Rest of 4.1, some of 4.2 as time permits (4.2 not on exam)
  • Exam Practice: 4.1 (p 158) #1, 2, 5, 7, 11, 12, 13, 19, 22
  • x-hour: chromatic polynomials (5.3)
• Week 6 (May 2-6):
  • k-connected graphs, planar graphs (4.2 to p 164 and 166-169, 6.1)
  • Quiz Practice: 4.2 (p 172) #1, 2, 4-6, 8, 11-14, 23, 35
  • x-hour: finishing Hamiltonian paths (7.2)
• Week 7 (May 9-13): Rebecca's office hours cancelled for Tuesday (5/10)
  • planar graphs: characterizing and some properties thereof (6.1 to p 235 and 241-242, 6.2 to p 251)
  • Quiz Practice: 6.1 (p 243) #1-3, 6; 6.2 (p 255) #1, 8, 11, 12; 7.2 (p 294) #2-5, 9, 12
  • x-hour: random graphs (8.5.3-9)
• Week 8 (May 16-20):
  • Ramsey theory; directed graphs (8.3 to p 382, p 386; see also Appendix A p 491-2; 1.4 to p 56, 1.4.17-18, p 60-63)
  • Quiz Practice: 6.1 (p 243) #8-10, 20, 27, 31; 8.3 (p 392) #17a, 25
  • x-hour: random graphs (8.5)
• Week 9 (May 23-27): no x-hour
  • directed graphs; touch of extremal problems; review (2.2 p 89-90; 4.2 p 164-166; 1.3 p 38-39)
  • Last Quiz Practice: 1.4 (p 63) #5, 7, 8, 11, 14, 19, 22, 29; 2.2 (p 92) #33, 35; 4.2 (p 172) #3, 7, 29; 8.5 (p 448) #1-4, 10
• "Week" 10 (June 1): final exam review
  • Final Exam Practice: 1.3 (p 47) #1-3, 7, 9, 14, 15, 17, 18, 36, 40, 41
• Final Exam: Saturday, June 4, 8-11 AM, Haldeman 28                                                review sheet

      Policies

Grading: Homework will be assigned but uncollected. It is only for preparation for quizzes and exams. There will be a quiz each Friday which will cumulatively count for 100 points (though they will likely not add up to 100; they will be scaled). The midterm will be 100 points and the final exam will be 150 points.

Honor Principle: On quizzes and exams, no help is to be given or received. Please feel free to consult each other and printed or online sources for help with the homework, in addition to the instructors.

Students with disabilities: I encourage students with disabilities, including "invisible" disabilities like chronic diseases and learning disabilities, to discuss with me any appropriate accommodations that might be helpful.

Last modified June 1, 2011