FALL 2008:  MATH 4022 (Intro to Graph Theory)
 
  Click here for an outline
 
  ALL HW PROBLEMS ARE FROM THE BOOK BY Douglas West,
  UNLESS SPECIFIED OTHERWISE:
-----------------------------------------------------------------------------------
 
  HOMEWORK 1 (Due: Wednesday, Sept. 3rd)
    Section 1.1: Problems 12, 16, 28, 30
    Section 1.2: Problems 20, 25, 27
    Section 1.3: Problems 41
    Optional Problems (no need to turn in): 1.1.25, 1.1.29, 1.2.8
   

  HOMEWORK 2 (Due: Monday, Sept. 15th)
    Section 1.3: Problems 8, 64
    Section 2.1: Problems 37
    Section 2.2: Problems 1, 9, 10, 17
    Section 2.3: Problem 7 (Hint should refer to 2.1.37, and not 2.1.34)
   
  TEST 1 (September 22nd)
  First three to be done in class;
  the FOURTH to be brought back to CLASS on WEDNESDAY, Sept. 24th
 
  HOMEWORK 3 (Due: Monday, Oct. 6th)
    Section 3.1: Problems 3, 28, 33, 37
    Section 3.3: Problems 10, 15, 16
 
  HOMEWORK 4 (Due: Monday, Oct. 27th)
    Section 4.1: Problems 1, 5, 7, 8, 28
    Section 4.2: Problems 1, 8, 24

  TEST 2 (October 31st)
  First three to be done in class;
  the 4th+5th to be brought back to CLASS on Monday, Nov. 3rd

  HOMEWORK 5 (Due: Monday, Nov. 24th)
    Section 5.1: Problems 1, 4, 28, 38
    Section 5.2: Problems 1, 22 * (see below)
    Section 5.3: Problems 1, 8
    Extra Problem: An n-set is monochromatic, if every element of the set gets
    the same color. A collection of n-sets has Property B, if there exists
    a 2-coloring (as in a Red-Blue coloring) of the elements so that no set is
    monochromatic. Show that every collection containing less than
    2^{n-1} sets (each being an n-set) has Property B.
    (Hint: use a random 2-coloring.)

(*) Sorry for the typo: the RANGE should be THREE MILES rather than 6 miles; everything else is good.
    Use Application 5.2.11 in the book to solve this.
    The problem is adapted (as acknowledged in the textbook) from Bondy-Murty,
    where the city has RADIUS 6 MILES and a range of NINE MILES for each transmitting
    station.

 *** FINAL EXAM on Wednesday, Dec. 10th, 11:30am -- 2:20pm (Room 246)
     Syllabus: Chapters 1-- 5 of Doug West's book.
     OPEN TEXT BOOK ***