MATH 485, GRAPH THEORY
(Introduction to the theory and applications of graphs and directed graphs.
Emphasis on the fundamental theorems and their proofs.)

Syllabus - Extra credit problems

• HWA-01, due Wed, Sep 4.
  • Read and understand: Chapter 1 in "Pearls" and Chapter 1 in "Extra pearls";
  • Start to read: Chapter 2; in "Perls"
  • Exercises: 1.1.1, 1.1.9, 1.2.7, 1.3.2 in "Pearls" and 1.3 in "Extra pearls";
  • (Bring a red pen.)
• HWA-02, due Mon, Sep 9.
  • Read: Chapter 2 in "Pearls";
  • Exercises: 1.1.7, 1.2.5, 1.3.4, 1.3.15, 2.1.5.
  • (Bring a red pen.)
• HWA-03, due Mon, Sep 16.
  • Read: Chapter 2 and Section 3.2 in "Pearls";
  • Exercises: 2.1.3, 2.1.4, 2.1.11, 2.2.1, 2.4.2.
  • (Bring a red pen.)
• HWA-04, due Mon, Sep 23.
  • Read and understand: Sections 2.4, 3.2 and 3.1 in "Pearls";
  • Start to read: Chapter 4 in "Pearls";
  • Exercises: 2.4.3, 2.4.21, 3.2.1, 3.1.11, 3.1.16.
  • (Bring a red pen.)
• HWA-05, due Mon, Sep 30.
  • Read Chapter 4 in "Pearls" and Chapter 2 in "Extra pearls";
  • Exercises: 2.1.24, 3.1.6, 4.1.1, 4.2.4, 4.3.4.
  • (Bring a red pen.)
• HWA-06, due Mon, Oct 7.
  • Read and understand: Chapter 2 in "Extra pearls";
  • Start to read: Chapter 5 in "Pearls" and Chapter 3 in "Extra pearls";
  • Exercises: 2.7, 2.10, 2.13 in "Extra pearls" and 5.1.2, 5.1.8 in "Pearls".
  • (Bring a red pen.)
• HWA-07, due Mon, Oct 14.
  • Read and understand: Chapter 5 in "Pearls" and Chapter 3 in "Extra pearls";
  • Exercises: 3.6 in "Extra pearls" and 5.2.4, 5.2.5, 5.3.1, 5.3.2 in "Pearls";
  • Prepare at least one question about the covered material.
  • (Bring a red pen.)
• Midterm, Fri Oct 18, in class, 5 problems, 100 points:
  • 2 theorems from the list: 1.1.2, 1.3.1, 1.3.2, 1.3.4, 1.3.5, 1.3.6, 2.1.2, 2.1.3, 2.1.6, 2.2.3, 2.2.4, 2.3.1, 2.3.2, 2.3.4, 2.3.5, 2.4.2, 3.1.2, 3.1.4, 3.1.5, 3.1.7, 3.2.1, 3.2.2(corrected in the appendix of "Extra pearls"), 4.1.3, 4.3.2 in "Pearls" and 2.5, 3.2, 3.5 in "Extra pearls".
  • 2 problems from HWA.
  • one new problem.
• HWA-08, due Mon, Oct 21.
  • Start to read: Chapter 4 in "Extra pearls";
  • Exercises: 4.1.5, 4.2.6, 5.3.8 in "Pearls" and 3.7, 4.4 in "Extra pearls".
  • (Bring a red pen.)
• HWA-09, due Mon, Oct 28.
  • Read: Chapters 4 and 5 in "Extra pearls";
  • Exercises: 4.8, 5.2, 5.6, 5.9, 5.11, 5.12(b,c) in "Extra pearls"
  • (Bring a red pen.)
• HWA-10, due Mon, Nov 4.
  • Read: Chapter 7 in "Pearls" and an addition to it in Appenix B in "Extra pearls";
  • Exercises: 5.2.11, 7.1.8, 7.1.9 in "Pearls" and 5.10, 6.4 in "Extra pearls"
  • (Bring a red pen.)
• HWA-11, due Mon, Nov 11.
  • Read: Chapter 6 in "Extra pearls"
  • Exercises: 6.8, 6.12, 6.13, 6.14 in "Extra pearls" and 7.3.5 in "Pearls".
  • (Bring a red pen.)
• HWA-12, due Mon, Nov 18.
  • Read: Chapters 8 and 9 in "Pearls";
  • Exercises: 8.4.11, 8.1.9, 8.1.14, 8.1.16, 8.3.3
  • (Bring a red pen.)
• HWA-13, due Mon, Dec 2.
  • Read: Chapter 9 in "Pearls" and Appendix C;
  • Try to read: Chapter 10 in "Pearls";
  • Exercises: 9.1.3, 9.1.7, 9.3.7, 9.3.12 (without the 4-color theorem) in "Pearls".
  • Draw K_3,4 on the torus.
  • (Bring a red pen.)
• HWA-14, due Mon, Dec 9.
  • Read: Chapter 7 in "Extra pearls" and Appendix C;
  • C.7, C.11 in Appendix C and
    7.6, 7.10, 7.14 in "Extra pearls".
  • (Bring a red pen.)

---

• Extra office hour: Tue Dec 17, 14:00--15:00, McAlister 333

---

• Final exam, Wed Dec 18, 16:40--18:30, Thomas Bldg 201; 8 problems:
  • 3 theorems from the following list:
    1.1.2, 1.3.1, 1.3.2, 1.3.5, 1.3.6,
    2.1.2, 2.1.3, 2.1.6, 2.2.3, 2.2.4, 2.3.1, 2.3.5, 2.4.2,
    3.1.2, 3.1.5, 3.1.7, 3.2.1, 3.2.2(corrected in the appendix of "Extra pearls"),
    4.1.3, 4.3.2,
    8.1.1, 8.1.2, 8.1.4, 8.1.5, 8.1.6, 8.1.7, 8.2.1, 8.2.3, 8.3.2, 8.4.1(corrected in the appendix of "Extra pearls"),
    9.1.4, 9.1.6, 9.1.7, 9.3.1(part 1) in "Pearls" and
    2.5, 3.2, 3.5, 4.7, 5.3, 5.4, 5.13, 6.5, 6.11, 7.7, 7.9, 7.11, 7.16, B.1 in "Extra pearls".
  • 3 problems from HWA
  • 2 new problems
  • Cheat sheet: you can bring a sheet of paper one side, with diagrams and formulas, no words allowed.