Graph Theory (Math 428, section 2), Fall 2025 (Rutgers, NB)

• Instructor: Dr. Doron Zeilberger (aka Dr. Z.) [Email: DrZlinear@gmail.com (only for this class)]

• Time: Tuesdays and Fridays, Period 2, 10:20-11:40 am

• Place: TILLETT HALL, ROOM 251 (Livingston Campus)

• Textbook: "Introduction to Graph Theory", fourth edition, by Robin Wilson [on-line]

• Dr. Z.'s Office Hours: Tuesdays and Fridays 2:30-3:40 pm, Hill 704

• Homework Grader: Mr. William Hu

• CLASS POLICY

• Tue., Sept. 2; Lecture 1 (Section 1) ; HW (due Mon., Sept. 8, 8:00pm): 1.2, 1.4 [but use your own family tree, starting with your grandfather or grandmother, or even sooner], 1.6, 1.7 (pp 6-7)
  [Here are Heidi So's nice answers]

  Here is the attendance quiz for Lecture 1
  and are the solutions to the attendance quiz for Lecture 1

  ---

• Fri., Sept. 5; Lecture 2 (Section 2) ; HW (due Mon., Sept. 15, 8:00pm): 2.2, 2.3, 2.4, 2.7, 2.9 (pp 14-16)

  Here is the attendance quiz for Lecture 2
  and are the solutions to the attendance quiz for Lecture 2 (thanks to Arav Sanwal)

  ---

• Tue., Sept. 9; Lecture 3 (Section 3); real quiz 1 (on Lecture 1) ; HW (due Mon., Sept. 15, 8:00pm): 3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7, 3.8 (pp 20-21)

  Here is the attendance quiz for Lecture 3
  and are the solutions to the attendance quiz for Lecture 3 (thanks to Dr. Z., new version. The previous version had two minor errors pointed out by Shakhti Venkatesan)
  Here is the real quiz 1
  and are the solutions to quiz 1 (thanks to Malaika Munzam) (average: 8 out of 8)

  ---

• Fri., Sept. 12; Lecture 4 (Section 4); HW (due Mon., Sept. 22, 8:00pm): 4.1, 4.2, 4.3, 4.4 (p. 25)

  Here is the attendance quiz for Lecture 4 and here is the Solution to the attendance quiz for lecture 4 (thanks to Dr. Z.)
  here is the directed graph
  [Compare wikipedia solution]

  ---

• Tue., Sept. 16; Lecture 5 (Section 5); real quiz 2 (on Lectures 2 and 3) ; HW (due Mon., Sept. 22, 8:00pm): 5.1, 5.2, 5.3, 5.5, 5.8, 5.9 (p. 30)

  Here is the real quiz 2 and are the solutions to quiz 2 (thanks to Holen Yee)
  (average: 4.67 out of 8)

  Here is the attendance quiz for Lecture 5 and here is the Solution to the attendance quiz for lecture 5 (thanks to Dr. Z.)

  ---

• Fri., Sept. 19; Lecture 6 (Section 5) ; HW (due Mon., Sept. 29, 8:00pm): 6.1, 6.2, 6.3, 6.4, 6.5, 6.6 (p. 34)

  Here is the attendance quiz for Lecture 6 and here is the Solution to the attendance quiz for lecture 6 (thanks to Dr. Z.)

  ---

• Tue., Sept. 23; Lecture 7 (Section 7) real quiz 3 (on Lectures 4 and 5) ; HW (due Mon., Sept. 29, 8:00pm): 7.1, 7.2, 7.3, 7.4, 7.5, 7.6 (p. 37)

  Guest Lecturer: Mr. Pablo Blanco

  Here is the attendance quiz for Lecture 7 and here is the Solution to the attendance quiz for lecture 7 (thanks to Dr. Z.) and here is Pablo Blanco's proof of Ore's theorem

  Here is the real quiz 3 and are the solutions to quiz 3 (thanks to Dr. Z.) (average: 4. 28 (out of 8))

  ---

• Fri., Sept. 26; Lecture 8 (Section 8); HW (due Mon., Oct. 6, 8:00pm): 8.1, 8.2, 8.3, 8.4, 8.6, 8. 7 (pp. 41-42)

  Here is the attendance quiz for Lecture 8 and here is the Solution to the attendance quiz for lecture 8 (thanks to Isha Shah)

  ---

• Tue., Sept. 30; Lecture 9 (Section 9) real quiz 4 (on Lectures 6 and 7) ; HW (due Mon., Oct. 6, 8:00pm): 9.1, 9.2, 9.3, 9.4, 9.5, 9.6, 9.7, 9.8 (p. 46)

  Here is the real quiz 4 and are the solutions to quiz 4 (thanks to Dr. Z.) (average= 6.03, out of 8)

  Here is the attendance quiz for Lecture 9 and here is the Solution to the attendance quiz for lecture 9 (thanks to Dr. Z.)

  ---

• Fri., Oct. 3; Lecture 10 (Section 10) ; Instead of the second proof in the book we are doing Joyal's proof

  HW (due Mon., Oct. 13, 8:00pm): 10.1, 10.2, 10.3 (p. 51) and
  additional problems: Find the endofunction (expressed as a list of integers of length 6 each between 1 and 6) corresponding to the doubly-rooted trees in Fig. 10.6 (p. 51) where the first root is 1 and the second root is 2.
  Also: find the doubly-rooted labeled trees on 7 vertices corresponding to (a) 1227336 (b) 2222777

  Here is the attendance quiz for Lecture 10 and here is the Solution to the attendance quiz for lecture 10 (thanks to Heidi So)

  ---

• Tue., Oct. 7; Lecture 11 (Section 11) real quiz 5 (on Lectures 8 and 9) ; HW (due Mon., Oct. 13, 8:00pm): 11.1, 11.2, 11.5, 11.6, 11.8, 11.9 (pp. 57-58)

  Here is real quiz 5 and are the solutions to quiz 5 (thanks to Malaika Munzam) (average=6.57 out of 8)

  Here is the attendance quiz for Lecture 11 and here is the Solution to the attendance quiz for lecture 11 (thanksto Arav Sanwal )

  ---

• Fri., Oct. 10; Special Maple class (in Computer Lab, Tillett-106J2)
  Special Maple homework (due Mon., Oct. 20, 8:00pm):

  ---

• Tue., Oct. 14; Lecture 12 (Section 12) real quiz 6 (on Lectures 10 and 11) ; HW(due Mon., Oct. 20, 8:00pm): 12.1, 12.2, 12.3, 12.4, 12.6, 12.7 (pp. 64)

  Here is the attendance quiz for Lecture 12 and here is the Solution to the attendance quiz for lecture 12 (thanks to Robin Wilson ) and here is an even better solution (thanks to Elinor Lvov )

  Here is real quiz 6 and are the solutions to quiz 6 (thanks to Jeff MacFarland) (average=6.28 out of 8)

  ---

• Fri., Oct. 17; Review for Exam 1

  Here is the attendance quiz for the review class and here are Solutions to attendance quiz for the review class

  ADDED Oct. 18, 2025: student Holen Yee kindly agreed to make public his Solutions to the Homework problems

  ---

• Tue., Oct. 21; Exam 1 (On lecture 1-12)

  Here is Exam 1 and here are the Perfect solutions to Exam 1 (thanks to Heidi So, who won the "Best Exam 1 award")
  Average: 83.72 (out of 100)

  Added Oct. 25, 2025: students who didn't do as well as they should have are welcome to join the Second Chance Club for Exam 1

  ---

• Fri., Oct. 24; Lecture 13 (Section 13) HW (due Mon., Nov. 3, 8:00pm): 13.1, 13.3, 13.4, 13.5, 13.6 (p. 69)

  Here is the attendance quiz for Lecture 13 and here is the Solution to the attendance quiz for lecture 13 (thanks to Arav Sanawal )

  ---

• Tue., Oct. 28; Lecture 14 (Platonic solids);

  Platonic solids, see also this nice page

  real quiz 7 (on Lecture 12);

  HW 14 (due Nov. 3, 8:00pm):

  (1) Fully understand, and be able to derive from scratch, all the five Platonic solids, and be able to explain that they are the only ones. (2) Expalin how to construct a soccer ball out of an icosahedron. How many vertices, edges, and faces does a soccer ball have? Verify Euler's formula.

  ---

• Fri., Oct. 31; Lecture 15 (Section 17); HW (due Nov. 10, 8:00pm): 17.1, 17.2, 17.3, 17.4, 17.5, 17.7 (pp. 85-86)

  ---

• Tue., Nov. 4; Lecture 16 (Section 20) ; real quiz 8 (on Lectures 13,14); HW(due Nov. 10, 8:00pm): 20.1, 20.2, 20.3, 20.4, 20.5, 20.6, 20.7 (p. 95)

  ---

• Fri., Nov. 7; Lecture 17 (Section 21); HW (due Nov. 17, 8:00pm): 21.1, 21.2, 21.3, 21.4, 21.5 (p. 99)

  ---

• Tue., Nov. 11; Lecture 18; (Ramsey's Theorem Part I) real quiz 9 (on Lectures 15,16); HW (due Mon. Nov. 17, 8:00pm): tba

  ---

• Fri., Nov. 14; Lecture 19; (Ramsey's Theorem Part 2) ; HW (due Mon. Nov. 24, 8:00pm): tba

  ---

• Tue., Nov. 18; Lecture 20 (Section 25) real quiz 10 (on Lectures 17,18); HW (due Nov. 24, 8:00pm): 25.1, 25.2, 25.3, 25.5 (pp. 114-115)

  ---

• Fri., Nov. 21; Lecture 21 (Section 26): HW (due Nov. 24, 8:00pm): 26.1, 26.2, 26.3, 26.4 (p. 117)

  ---

• Tue., Nov. 25; Review for Exam 2

  ---

• Wed., Nov. 26; Exam 2 (on Lectures 1-20)

  ---

• Tue., Dec. 2; Lecture 22 (Combinatorial Games Part I); HW (due. Mon. Dec.8, 8:00pm): tba

  ---

• Fri., Dec. 5; Lecture 23 (combinatorial Games Part II) HW (due. Mon. Dec.8, 8:00pm): tba

  ---

• Tue., Dec. 9; REVIEW for the Final Exam

  ---

• Final Exam: Thurs., Dec. 19, 2025, 8:00-11:00 am (IN CLASSROOM)

  ---

  Doron Zeilberger's teaching page