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 ( wsh24@scarletmail.rutgers.edu)

• 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.

  Here is the attendance quiz for Lecture 14 and here is the Solution to the attendance quiz for lecture 14 (thanks to Robert Cannuni)

  Here is real quiz 7. For the solutions see bottom half of p. 61 of Robin Wilson's book. (average=7.66 out of 8)

  ---

• 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)

  Here is the attendance quiz for Lecture 15 For the solutions see bottom half of pp. 83-84 of Robin Wilson's book.

  ---

• 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)

  Here is the attendance quiz for Lecture 16 and here are the solutions (thanks to Arav Sanwal) (see also p. 93 of Robin Wilson's book)

  real quiz 8. Here is Solutions to real quiz 8 (thanks to former students April Prinzo and Sarah Shepherd) (See also wikipedia article on Platonic solids) (average=6.39 out of 8)

  ---

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

  Here is the attendance quiz for Lecture 17 and here are the solutions (thanks to Dr. Z.)

  ---

• Tue., Nov. 11; Lecture 18; (Ramsey's Theorem Part I) following the wikipedia article, and the very nice overview by Carnegie-Mellon professor Alan Frieze (only slides 1-15)

  real quiz 9 (on Lectures 15,16);

  Here is real quiz 9. and is solutions to real quiz 9 (thanks to Robin Wilson) (average=5.62)

  Here is attendance quiz, and here are the solutions (thanks to Dr. Z.)

  HW18 (due Mon. Nov. 17, 8:00pm):
  (1) State and prove Ramsey's theorem about 2-coloring the complete graph K_N
  

  ---

• Fri., Nov. 14; Lecture 19; (Ramsey's Theorem Part 2) following the wikipedia article, and the very nice overview by Carnegie-Mellon professor Alan Frieze (only slides 1-15)

  HW19 (due Nov. 24, 2025)

  (1) Use Ramsey's theorem with two colors to prove Ramsey's theorem about r-colorings, for any number of colors.
  (2) Prove that R(k,k) > 2^k/2

  Here is attendance quiz, and here are the solutions (thanks to Dr. Z., based on wikipedia)

  ---

• 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 (pp. 114-115) . Also: "State and prove Hall's Marriage Theorem"

  Here is real quiz 10. and is solutions to real quiz 10 (thanks to Holen Yee) [average=6.33 (out of 8)]

  ---

• Fri., Nov. 21; Review for Exam 2

  student Holen Yee kindly agreed to make public his Solutions to the Homework problems (until HW22)

  ---

• Monday, Nov. 24, 2025, 6:00 -7:30 pm: OPTIONAL REVIEW FOR EXAM 2 (but mandatory for members of sccI), via WebEx. (Invitations were sent.)

  ---

• Tue., Nov. 25; NO CLASS

  ---

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

  Here is Exam 2 and here are Perfect solutions (thanks to Holen Yee) and also Equally Perfect solutions (thanks to Heidi So) (average=89.3 [out of 100])

  ---

• Tue., Dec. 2; Lecture 21 (Section 27, only the first two pages. You should know the statement and proof of Theorem 27.1 but only the statement of Theorem 27.2): HW (due Dec. 8, 8:00pm): 27.1, 27.2, 27.4 (p. 121) Additional homework: if currently Ms. 1 knows but is not married to Mr. a; Ms 2 is married to Mr. a and knows Mr. b, Ms. 3 is married to Mr. b and knowns Mr. c, Ms. 4 is married to Mr. c and knows Mr. d. After applying the alternating path algorithm, who are now the married couples?

  Here is today's attendance quiz, and here are the solutions (thanks to Shilpi Shah)

  ---

• Fri., Dec. 5; Lecture 22 (combinatorial Games) real quiz 11 (on Lecture 20)

  Dr. Z.'s notes

    wiki

  HW (due. Mon. Dec.8, 8:00pm): See Dr. Z.'s notes

  student Holen Yee kindly agreed to make public his Solutions to the Homework problems (until HW22)

  Here is today's quiz 11, for the solution see p. 113 of the book. (average=5.62 (out of 8))

  ---

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

  ---

  Wed., Dec. 17, 7:00-8:30 pm: OPTIONAL REVIEW FOR THE FINAL (via WebEx)

  ---

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

  ---

  Doron Zeilberger's teaching page