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

(Last Update: Dec. 24, 2023) http://sites.math.rutgers.edu/~zeilberg/math438_f23.html

Instructor: Dr. Doron Zeilberger (aka Dr. Z.) [Email: ShaloshBEkhad@gmail.com (only for this class)]
Time: Mondays and Thursdays, Period 3, 12:10-1:30pm
Place: TILLET HALL, ROOM 105 (Livingston Campus) Note room change!
Textbook: "Introduction to Graph Theory", fourth edition, by Robin Wilson [on-line]
Dr. Z.'s Office Hours: Mth 9:00-10:10am, TILLET 105
Homework Grader: Mr. Shrey Patel (shrey.patel@rutgers.edu)
CLASS POLICY

Schedule and Homework

Thurs., Sept. 7:
Lecture 1: Section 1
HW1 (due 9/13, 10:00 pm): Section 1 (pp. 6-7): 1.2, 1.4, 1.6, 1.7; Also draw all the labeled trees with 4 vertices, how many are there? Also draw all the unlabeled trees with 4 vertices, how many are there?
Here are the solutions (thanks to Daniel Teytel)
Here is attendance quiz 1 and here are the Solutions to attendance quiz 1 .
Mon., Sept. 11:
Lecture 2: Section 2
HW2 (due 9/20, 10:00pm): Section 2 (pp. 14-16): 2.2, 2.3,2.4, 2.7, 2.9 [Hint: If it has no vertex of degree 0, then the degree sequence is 1<=d1<=...<=dn<=n-1, can these n numbers be distinct?. If it has one vertex of degree 0 remove it, and use induction. If it has at least two such vertices, you are done], 2.12, 2.13

Here are the solutions (thanks to Franklin Yin)
Here is attendance quiz 2 and here are the Solutions to attendance quiz 2 (thanks to Donald Yeh).
Thurs., Sept. 14:
Lecture 3: Section 3
HW3 (due 9/20, 10:00pm): Section 3 (pp. 20-21): 3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7, 3.8
Here are the solutions (thanks to April Rose Prinzo)
real quiz 1 (on Lecture 1) [during the first ten minutes of the class]
Here is attendance quiz 3 and here are the Solutions to attendance quiz 3 (thanks to Zixin Qu)
Here is Real quiz 1 and here are the Solutions to Real quiz 1 (thanks to Nancy Ezeifeoma). average=8 (out of 8)
Mon., Sept. 18:
Lecture 4: Section 4
HW4 (due 9/27, 10:00pm): Section 4 (p. 25): 4.1, 4.2, 4.3, 4.4
Here are the solutions (thanks to Zixin Qu)

Here is attendance quiz 4 . Solution coming up. Solutions to attendance quiz 4 (thanks to Pranay Kumar)
Thurs., Sept. 21:
Lecture 5: Section 5
HW5 (due 9/27, 10:00pm): 5.1, 5.2, 5.3, 5.4, 5.5. 5.6, 5.7, 5.8, 5.9
Here are the solutions (thanks to Tyler Harper)
real quiz 2 (on Lectures 2, 3) [during the first ten minutes of the class]

Here is attendance quiz 5 and here are the Solutions to attendance quiz 5 (thanks to Tyler Harper)
Here is Real quiz 2 and here are the solutions to Real quiz 2 (thanks to Vishal Agarwal) average=5.4 (out of 8)
Mon., Sept. 25: Guest-Lecturer: Ms. Kaylee Weatherspoon
Lecture 6: Section 6
HW6 (due 10/4, 10:00pm): 6.1, 6.2, 6.3, 6.4, 6.5, 6.6
Here are the solutions (thanks to Nancy Ezeifeoma)

Here is attendance quiz 6 and here are the Solutions to attendance quiz 6 .
Thurs., Sept. 28:
Lecture 7: Section 7
HW7 (due 10/4, 10:00pm): 7.1, 7.2, 7.3, 7.4, 7.5, 7.6, 7.7
Here are the solutions (thanks to Nuray Kutlu)
real quiz 3 (on Lectures 4, 5) [during the first ten minutes of the class]

Here is attendance quiz 7 and here are the Proof wiki's solution (this is better than the proof in the book)
Here is Real quiz 3 and here are the solutions to Real quiz 3 average=6.69 (out of 8)
Mon., Oct. 2:
Lecture 8: Section 8 (pp. 104-112)
HW8 (due 10/11,10:00pm): 8.1, 8.2, 8.3, 8.4, 8.6, 8.7

Here is attendance quiz 8 and here are the Solutions to attendance quiz 8 (thanks to Shivam Patel)
Thurs., Oct. 5:
Lecture 9: Section 9
HW9 (due 10/11,10:00pm): 9.1, 9.2, 9.3, .4, 9.5.9.6,9.7, 9.8
real quiz 4 (on Lectures 6, 7) [during the first ten minutes of the class]

Here is attendance quiz 9 and here are the Solutions to attendance quiz 9
Here is Real quiz 4 and here are the Solutions to real quiz 4 average=6.34 (out of 8)
Mon., Oct. 9:
Lecture 10: Section 10
Andre Joyal's beautiful proof of Cayley's formula
HW10 (due 10/18, 10:00pm): 10.1, 10.2, 10.3 [Hints: (i) if you remove that specific vertex from a labeled tree with n vertices, you would get a smaller labeled tree with n-1 vertices, but you need to keep track of the neighbor of that removed vertex] (ii) Use one of the definitions of e, and calculus],10.5 (optional, if you do it, do K_2,2 instead of K_2,3).
Also: Additonal mandatory problems:
1: Apply the Joyal mapping to the each of the true trees in excercise 10.2 where (a) they are made doubly-rooted with the initial root is 6 and the terminal root is 3. (b) they are made doubly-rooted with the initial root is 1 and the terminal root is 2. (Note that these are really four distinct problems).
2: What is the doubly rooted tree, on nine vertices, corresponding to the endofunction
f(1)=3,f(2)=3, f(3)=1 , f(4)=2 , f(5)=9 , f(6)=3 , f(7)=4 , f(8)=2 , f(9)=7 .

Here is attendance quiz 10 and here are the Solutions to attendance quiz 10 .
Thurs., Oct. 12:
Lecture 11: Section 11
HW11: 11.1, 11.2, 11,5, 11.6, 11.8, 11.9
real quiz 5 (on Lecture 8, 9) [during the first ten minutes of the class]

Here is attendance quiz 11 and here are the Solutions to attendance quiz 11 (thanks to Nuray Kutlu)
Here is Real quiz 5 and here are the solutions to Real quiz 5 (thanks to Vishal Agrawal) average=7.0 (out of 8)
Mon., Oct. 16: Special Lecture: Using Maple to handle graph theory
SPECIAL CLASSROOM: Tillett 106J1 (Inside Tillet Computer Lab, close to our usual classroom)
HW: (due 10/25, 10:00pm) hwMaple.txt
Thurs., Oct. 19:
Lecture 12: Section 12
HW12 (due 10/25, 10:00pm): 12.1, 12.2, 12.3, 12.4, 12.6, 12.7
real quiz 6 (on Lectures 10, 11) [during the first ten minutes of the class]

Here is attendance quiz 12 and here are the Solutions to attendance quiz 12 (thanks to April Prinzo)
Here is Real quiz 6 and here are the solutions to Real quiz 6 (thanks to Zixin Qu) average=7.65 (out of 8)
Mon., Oct. 23: Review Solutions to attendance quiz for Review class (thanks to Jason Sanghvi )
Thurs., Oct. 26: EXAM 1 (On Lectures 1-12) .
Here is Exam 1, and here are student George Basta's perfect answers to Exam 1. average=91.8 (out of 100) (standard-deviation=10.2) [ George won a $25 amazon gift card for the best exam 1 prize]
Mon., Oct. 30:
Lecture 13: Section 13
HW13 (due 11/8, 10:00pm): 13.1, 13.3, 13.4, 13.5, 13.6

Here is attendance quiz 13 and here are the Solutions to attendance quiz 13 (thanks to Sarah Shepherd)
Thurs.,Nov. 2:
Lecture 14: Platonic solids, see also this nice page
HW14 (due 11/8,10: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.

real quiz 7 (on Lecture 12) [during the first ten minutes of the class]

Here is Real quiz 7 and here are the solutions to Real quiz 7 (Thanks to Sarah Shepherd) average=7.62 (out of 8)
Here is attendance quiz 14 and here are the Solutions to attendance quiz 14 (thanks to Leo Hernandez)
Mon., Nov. 6:
Lecture 15: Section 17
HW15 (due 11/15, 10:00pm): 17.1, 17.2, 17.3, 17.4, 17.5, 17.7

Here is attendance quiz 15 and here are the Solutions to attendance quiz 15 (thanks to Sarah Shepherd). [Also see wikipedia page]
Thurs., Nov. 9:
Lecture 16: Section 20
HW16 (due 11/15, 10:00pm): 20.1, 20.2, 20.3, 20.4, 20.5, 20.6, 20.7
real quiz 8 (on Lectures 13,14) [during the first ten minutes of the class]

Here is Real quiz 8 and here are the solutions to Real quiz 8 (thanks to April Prinzo and Sarah Shepherd) average=7.23 (out of 8)
Here is attendance quiz 16 and here are the Solutions to attendance quiz 16 (thanks to Sarah Shepherd ).
Mon., Nov. 13:
Lecture 17: Section 21
HW17 (due 11/20, 10:00pm): 21.1, 21.2, 21.3, 21.4, 21.5
Here is attendance quiz 17 and here are the Solutions to attendance quiz 17 (thanks to George Basta).
Thurs., Nov. 16:
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)
HW18 (due 11/20, 10:00pm):
(1) Prove Ramsey's theorem about 2-coloring the complete graph K_N

real quiz 9 (on Lectures 15,16) [during the first ten minutes of the class]

Here is Real quiz 9 and here are the solutions to Real quiz 9 (thanks to April Prinzo Nancy Ezeifeoma) average=6.81 (out of 8)
Here is attendance quiz 18 and here are the solutions (thanks to Professor Alan Friez, first six slides)
Mon., Nov. 20:
Lecture 19: Ramsey's Theorem Part II following the wikipedia article, and the very nice overview by Carnegie-Mellon professor Alan Frieze (only slides 1-15)
HW 19 (due 12/6, 10:00pm):
(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 19 (same as the one for Lecture 18) and here are the Solutions to attendance quiz 19 (thanks to Jason Saghvi and Leonardo Hernandez)
Tue., Nov. 21: note change
Lecture 20: Section 25
real quiz 10 (on Lectures 17,18) [during the first ten minutes of the class] average=5.54 (out of 8)
Here are the solutions to Real quiz 10 (thanks to Nancy Ezeifeoma and Vishal Agrawal)
HW20 (due 12/6, 10:00pm): 25.1, 25.2, 25.3, 25.5
Mon., Nov. 27: Review ; note change
Here are the solutions to today's attendance quiz (thanks to Zixin Qi, Niketan Baranwal, and Nancy Ezeifeoma)
Thurs., Nov. 30: EXAM 2 (On Lectures 1-19, with some emphasis on Lectures 13-19) . note change average=85.6 (out of 100)

Here is Exam 2, and here are student Nancy Ezeifeoma's perfect answers to Exam 2, and student April Prinzo's equally perfect answers to Exam 2
[ Nancy and April each won a $25 amazon gift card for the best exam 2 award]
Mon., Dec. 4:
Lecture 21: Section 26 (only Theorem 26.1); Section 27 (only Theorem 27.1); Section 29 (only Theorem 29.1)
HW21 (due 12/6, 10:00pm): 26.1, 26.2; 27.1, 27.2; 29.1, 29.2, 29.3
Recommended reading: D.R. Fulkerson's Feb. 1966 American Monthly paper, that won the prestigious Lester R. Ford award for 1967.
(BTW, the award is named after L.R. Ford, Sr., the father of the Ford from Fulkerson-Ford).
(BTW, another paper, that also won the Lester R. Ford award, but for 1990, is this gem .)
Thurs., Dec. 7:
Lecture 22: Combinatorial Games
Dr. Z.'s notes wiki
HW22 (due 12/13, 10:00pm): see Dr. Z.'s notes Here are the perfect solutions (thanks to Leonardo Hernandez).
Mon., Dec. 11: Review .
Final Exam: Thurs., Dec. 21, 2023, 12:00-3:00pm (IN CLASSROOM, TIL-105)
Here is Final Exam, and here are student April Prinzo's almost perfect answers to Exam 2
[April won the "Best Final Exam award", an amazon gift card for $30.]
The answer to 3(b) is wrong: The new flows (along this particular augmenting path) are: 6,8,2,0,9 [you add 3 to the current flows of the forward-pointing edges, and subtract 3 from the backward-pointing edges]

average=185.69 (out of 200) (s.d=14.32)
teaching evaluations.

Doron Zeilberger's teaching page