640:428:B1 Graph Theory, Summer 2007
Course info

News

Links

Requirements

Syllabus

Assignments

Homework #5 - due Tuesday, July 3
  • 25.6-ii (4 pts)
  • 26.2-iii, iv (2 pts) (The question here is: for each family, either find a transversal/SDR or show that Hall's condition does not hold)
  • 27.1 (2 pts)
  • 28.2 (4 pts), 28.3 (6 pts), 28.6 (2 pts)
  • 29.1 (2 pts), 29.7-i (4 pts)
  • Problems not in Wilson:
    E1 Show that Tutte's Theorem implies Hall's Theorem (4 pts)
    E2 Show that the Konig-Egervary Theorem (as stated in the handouts) implies Hall's Theorem (4 pts)
    E3 Recast the problem of constructing Latin squares as a graph coloring problem. (4 pts)

    Notes: Maximum score is 25 points, out of 38 available.

    • Homework #4 - due Wednesday, June 27
  • 20.7 (2 pts), 20.8 (6 pts), 20.10 (6 pts)
  • 21.1 (3 pts), 21.3-ii (2 pts), 21.4-i (3 pts)
  • 22.3 (2 pts), 22.4 (4 pts), 22.5-i,ii (5 pts)
  • 23.4-i (2 pts), 23.6 (4 pts), 23.7-i,iii (4 pts)
  • 25.2 (3 pts), 25.3 (2 pts), 25.5 (4 pts), 25.6-i (5 pts)
  • Write a detailed proof of Brooks' Theorem, following the ideas of section 18 (but using your own words) (6 pts)

    Notes: Maximum score is 45 points, out of 63 available.

    • Special Homework - due Thursday, June 21
    Do the following problems from the midterm exam:

    2-b (2 pts), 3-a,b (3 pts), 6 (4 pts), 7-b (3 pts), 8 (3 pts)

    Notes: Maximum score is 15 points, out of 15 available.

    Homework #3 - due Tuesday, June 19
  • 14.3 (2 pts), 14.4-i (3 pts), 14.6 (5 pts)
  • 15.3 (2 pts), 15.5 (2 pts), 15.6-i (2 pts), 15.10-i (3 pts)
  • 16.1 (2 pts), 16.4-i (3 pts)
  • 17.2 (4 pts), 17.7 (2 pts), 17.8 (6 pts), 17.12-i (4 pts)

    Notes: Maximum score is 30 points, out of 40 available.

    • Homework #2 - due Tuesday, June 12
  • 8.4 (4 pts)
  • 9.3 (3 pts), 9.8-i (2 pts), 9.9 (6 pts), 9.11-i (4 pts)
  • 10.3 (6 pts), 10.5 (6 pts)
  • 11.2 (3 pts), 11.9 (2 pts), 11.11 (4 pts)
  • 12.2 (3 pts), 12.4 (3 pts), 12.6 (4 pts)
  • 13.2 (2 pts), 13.3 (3 pts), 13.5-i (3 pts), 13.7 (5 pts)

    Note: Maximum score is 45 points, out of 63 available.

    • Homework #1 - First part - due Thursday, May 31
  • 2.8 (6 pts), 2.13-i (2 pts), 2.14-i (2 pts)
  • 3.5-iii, iv (3 pts), 3.7 (3 pts), 3.9-i, iii (4 pts)
  • 5.5-iii (2 pts), 5.6 (5 pts)

    Notes: Maximum score is 20 points, out of 27 available. For this assignment (and only for this one), you are required to work by yourself, with no communication with the other students in the course. But it is okay to ask me for hints.

    • Homework #1 - Second part - due Tuesday, June 5
  • 5.7-i (3 pts), 5.9 (5 pts), 5.10 (5 pts)
  • 6.3-ii, iii (2 pts), 6.6-i (3 pts)
  • 7.3-iii (2 pts), 7.4 (3 pts), 7.5 (5 pts)

    Note: Maximum score is 20 points, out of 28 available.