MATH 412 - Graph Theory (Fall 2023)

| General Information | Homework | Lecture Notes | Other Resources |

At its essence, graph theory is the abstraction and distillation of connection. On a small scale, this is very simple: each pair of vertices either is connected by an edge, or it isn't. But on the larger scale of the whole graph, out of these simple binaries arises astounding complexity and structure. Graph theory is distinctively positioned in mathematics as a subject that is very much pure math, with lemmas and theorems and proofs, but at the same time has numerous direct applications in close proximity to the pure math that is our focus in this course.

General Information

Lecture	MWF 10:00am-10:50am Henry Administrative Building 156
Textbook	Douglas B. West Introduction to Graph Theory, 2nd Edition Chapters 1-7
Instructor	Andrew Hardt Office: CAB 69B Email: ahardt@illinois.edu Office Hours: MF 11:00am-12:00pm, CAB 69B
More Details	Syllabus | Gradescope | If you can't access the Gradescope course, email me

Homework

Homework assignments are weekly, due at 9am on Wednesdays via Gradescope. Using LaTeX for your homework is encouraged, and you will receive 2 bonus points for each homework you typeset using LaTeX.

• Homework 1 (TeX file) -- due Wed. 8/30 at 9am (Solutions)
• Homework 2 (TeX file) -- due Wed. 9/6 at 9am (Solutions)
• Homework 3 (TeX file) -- due Wed. 9/13 at 9am (Solutions)
• Homework 4 (TeX file) -- due Wed. 9/27 at 9am (Solutions)
• Homework 5 (TeX file) -- due Wed. 10/4 at 9am (Solutions)
• Homework 6 (TeX file) -- due Wed. 10/11 at 9am (Solutions)
• Homework 7 (TeX file) -- due Wed. 10/25 at 9am (Solutions)
• Homework 8 (TeX file) -- due Wed. 11/8 at 9am (Solutions)
• Homework 9 (TeX file) -- due Thurs. 11/30 at 9am (Solutions)

Lecture Notes

• Lecture 1 (8/21): Syllabus, course overview
• Lecture 2 (8/23): Section 1.1
• Lecture 3 (8/25): Section 1.1 (cont.)
• Lecture 4 (8/28): Section 1.1 (cont.), Section 1.2
• Lecture 5 (8/30): Section 1.2 (cont.)
• Lecture 6 (9/1): Section 1.2 (cont.)
• Lecture 7 (9/6): Section 1.2 (cont.), Section 1.3
• Lecture 8 (9/8): Section 1.3 (cont.)
• Lecture 9 (9/11): Section 1.3 (cont.), Section 1.4
• Lecture 10 (9/13): Section 1.4 (cont.)
• Lecture 11 (9/15): Section 1.4 (cont.)
• Lecture 12 (9/18): Section 2.1
• Lecture 13 (9/20): Exam 1 Review
• Lecture 14 (9/22): Section 2.1 (cont.), Section 2.2
• Lecture 15 (9/25): Section 2.2 (cont.)
• Lecture 16 (9/27): Section 2.2 (cont.), electrical circuits
• Lecture 17 (9/29): Electrical circuits (cont.)
• Lecture 18 (10/2): Section 2.3
• Lecture 19 (10/4): Section 2.3 (cont.), Section 3.1
• Lecture 20 (10/6): Section 3.1 (cont.)
• Lecture 21 (10/9): Section 3.1 (cont.), Section 3.2
• Lecture 22 (10/11): Section 3.2 (cont.), Section 3.3
• Lecture 23 (10/13): Section 3.3 (cont.)
• Lecture 24 (10/16): Section 4.1
• Lecture 25 (10/18): Exam 2 Review
• Lecture 26 (10/20): Section 4.2
• Lecture 27 (10/23): Section 4.2 (cont.)
• Lecture 28 (10/25): Section 4.2 (cont.)
• Lecture 29 (10/30): Section 4.3
• Lecture 30 (11/1): Section 4.3 (cont.)
• Lecture 31 (11/3): Section 5.1
• Lecture 32 (11/6): Section 5.1 (cont.), Section 5.2
• Lecture 33 (11/8): Section 5.2 (cont.), Section 5.3
• Lecture 34 (11/10): Section 5.3 (cont.), Section 6.1
• Lecture 35 (11/13): Section 6.1 (cont.)
• Lecture 36 (11/15): Exam 3 Review
• Lecture 37 (11/17): Section 6.1 (cont.)
• Lecture 38 (11/29): Section 6.1 (cont.), Section 6.3
• Lecture 39 (12/1): Section 6.3 (cont.)
• Lecture 40 (12/4): Section 6.3 (cont.)
• Lecture 41 (12/6): Final exam review
• Review Session (12/12)

Important Course Events

Midterm Exam 1: Wednesday, 9/20, 7:00pm-8:30pm, Noyes Laboratory 217 (Solutions)
Midterm Exam 2: Wednesday, 10/18, 7:00pm-8:30pm, Noyes Laboratory 217 (Solutions)
Midterm Exam 3: Wednesday, 11/15, 7:00pm-8:30pm, Noyes Laboratory 217 (Solutions)
Final Exam: Thursday 12/14 -- 8:00am-11:00am, 132 Bevier Hall (Solutions)

Quiz 1: Friday, 9/15 (in class)
Quiz 2: Friday, 10/13 (in class)
Quiz 3: Friday, 11/10 (in class)
Quiz 4: Monday, 12/4 (in class)

Problem Sessions: Tuesdays, 4:00pm-5:30pm in Henry Administration Building 156

Background and Other Resources

Background

MATH 347, MATH 348, CS 374, or equivalent experience. Since this is a proof-based course, please talk to me if you don't have proof-writing experience.

Other Resources

• Overleaf, a cloud-based LaTeX editor
• Detexify, a web app for identifying the LaTeX command(s) for various symbols
• GraTeX, a free tool for generating TikZ code for graphs
• Guidelines for Good Mathematical Writing, by Francis Su
• Postnikov (MIT) lecture notes,
• Appel-Haken proof of Four-Color Theorem
• Article on Four-Color Theorem
• Article on a formal proof of the Four-Color Theorem