# Math 485: Graph Theory

I am Stephen G. Simpson, a Professor of Mathematics at Penn State University.

Math 485 is an introductory course on graph theory. I taught it in Fall 2009. The textbook was West, Introduction to Graph Theory, Second Edition. Here are some course materials.

• Initial Handout: DVI, PS, PDF.
• Homework #1: Section 1.1, pages 14-18, Exercises 12, 13, 14, 20, 22, 25, 26. Due Wednesday, September 9.
• Solutions to Homework #1: DVI, PS, PDF.
• Homework #2: Section 1.2, pages 31-34, Exercises 8, 20, 21, 30. Section 1.3, pages 47-53, Exercises 21, 24, 26. Section 1.4, pages 63-66, Exercises 11, 14, 18, 22, 27. Due Monday, October 5.
• Solutions to Homework #2: DVI, PS, PDF.
• Homework #3: Section 2.1, pages 75-80, Exercises 29, 35, 37. Section 2.2, pages 92-95, Exercise 18. Section 2.3, pages 103-106, Exercises 8, 10, 13, 14, 15. Also, letting $L_n$ be the $n$-ladder,
• Find a recursion formula for $\tau(L_n)$.
• Use your recursion to calculate $\tau(L_n)$ for $n=1,2,\ldots,10$.
• Solve your recursion to get an explicit formula for $\tau(L_n)$.
• Find $\lim_{n\to\infty}\tau(L_{n+1})/\tau(L_n)$.
Due Monday, October 26.
• Solutions to Homework #3: DVI, PS, PDF.
• Study Guide for Midterm Exam: DVI, PS, PDF.
• Midterm Exam: DVI, PS, PDF.
• Solutions to Midterm Exam: DVI, PS, PDF.
• Homework #4: Section 3.1, pages 118-123, Exercises 8, 19, 24, 25. Section 3.2, pages 134-136, Exercise 6. Section 6.1, pages 243-246 63-66, Exercises 12, 25, 35. Section 6.2, pages 255-256, Exercise 6. Due Friday, December 4.
• Solutions to Homework #4: DVI, PS, PDF.
• Study Guide for Final Exam: DVI, PS, PDF.
• Final Exam: DVI, PS, PDF.
MIDTERM EXAM: Monday, November 9, in class.

FINAL EXAM: Monday, December 14, 8:00 AM, 114 Ag Engr.

simpson@math.psu.edu   /   17 December 2009