# CS150-GT    Graph Theory Spring 2023

The Petersen graph labeled as a Kneser graph

STCs: JCC 270,   6:00-7:15pm

Instructor: Michael Jahn (Michael.Jahn@tufts.edu)

Office Hours:

 Michael Jahn: 1:00-3:00pm Fri  in JCC 320 also Tues after 12:00 is ok, but email me beforehand. I don't have a room booked, but we can probably go to the HRI Lab (conference room?) Adam Xu: 4:30-6:30pm Tues/Thurs  in JCC 501 Note: Adam's Tues office hours are cancelled, but you can still make an appointment with Michael Jahn if you need office hours on Tuesdays.

Text: Introduction to Graph Theory, 2e, by Douglas West

Other texts you might look at:

• Graph Theory and Its Applications 3e, by Gross, Yellen, Anderson (the 2e is even better in some ways)
• Introduction to Graph Theory 5e, by Wilson
• Graph Theory, by Bondy, Murty
• Graph Theory, by Diestel

• 20% = Weekly HW
• 20% = Quizzes
• 20% = Midterm1
• 20% = Midterm2
• 20% = Project

HW, Handouts, etc.: will be posted at https://www.cs.tufts.edu/comp/150GT/documents/
and an archive of all the docs from class are archived here: https://www.cs.tufts.edu/comp/150GT/documents/CLASS-DOCS.pdf

Homework: PDF submission to Gradescope. LaTeX preferred. Please no scans of handwritten solutions.

Project: There is no required programming in this course. But your project may be an implementation, or it may be a theoretical project.

Guidelines for write-ups: On any HW or Project (even on an Exam, as much as possible) you should present your solution with your fellow students in mind as the audience, not me. Level-of-detail is determined by what your classmates need to see, in order to understand your solution without having to solve the problems for themselves.

## Schedule by Lecture

 Week 1 L1 Wed, 18 Jan 2023 §1.1 intro/def of graphs hw1-including-pics.zip hw1.pdf hw1.tex Week 2 L2 Mon, 23 Jan 2023 §1.1 isomorphism walks, trails, paths L3 Wed, 25 Jan 2023 §1.2 connected, cut-edge, closed odd walk contains odd cycle indep set, bipartite graph, G bipartite iff no odd cycle hw2.pdf hw2.tex Week 3 L4 Mon, 30 Jan 2023 §1.2 §1.3 QUIZ 1 Eulerian circuits Handshaking lemma L5 Wed, 1 Feb 2023 §1.3 Counting cycles, vertex deletions, graphic sequences hw3.pdf hw3.tex Week 4 L6 Mon, 6 Feb 2023 §1.3, §2.1 extremal problems, trees and distance L7 Wed, 8 Feb 2023 §2.2, p.81 QUIZ 2 Prufer sequences (for counting labeled trees) hw4.pdf hw4.tex Week 5 L8 Mon, 6 Feb 2023 §2.3, p.101 §2.2, p.87 Huffman codes Graceful labeling See also graceful-labeling-algorithms-and-complexity.pdf, and the standard reference on labeling, Gallian's ongoing survey (currently in its 25th edition). There's a link to the pdf on that page. L9 Wed, 15 Feb 2023 §2.1 QUIZ 3 distance, diameter, eccentricity, radius, center, Weiner index hw5.pdf hw5.tex Week 6 Mon, 20 Feb 2023 HOLIDAY (Presidents' Day) L10 Wed, 22 Feb 2023 §5.1 vertex colorings, χ(G), k-critical, α(G), ω(G), join, cartesian product L11 THU, 23 Feb 2023 §5.1 §5.2 Brooks' Theorem The paper Brooks' Theorem and Beyond.pdf gives a proof of Brooks using Kempe-chains, along with several other proofs using different approaches. Week 7 Mon, 27 Feb 2023 EXAM 1 (on material up through Feb 15 in class, Chapters 1, 2) L 12 Wed, 1 Mar 2023 §5.2 §5.3 Mycielski's construction χG(k) = chromatic polynomial (of a graph G) hw6.pdf hw6.tex Week 8 L 13 Mon, 6 Mar 2023 §6.1 Planar embeddings L 14 Wed, 8 Mar 2023 §6.2 Euler's Theorem, subdivision, k-connectivity hw7.pdf hw7.tex Week 9 L 15 Mon, 13 Mar 2023 §6.2 Kuratowski's theorem L 16 Wed, 15 Mar 2023 §6.3 QUIZ 4 (on HW 6) PROJECT PROPOSAL DUE Coloring planar graphs: 5-color Theorem (using Kempe-chains) hw8.pdf (Not graded--do not turn in) hw8.tex Week 10 Mon, 20 Mar 2023 SPRING Wed, 22 Mar 2023 BREAK Week 11 L 17 Mon, 27 Mar 2023 §7.1 Edge coloring L 18 Wed, 29 Mar 2023 §7.2, 7.3 Vizing's Theorem Hamiltonian Cycles hw9.pdf hw9.tex Week 11 L 19 Mon, 3 Apr 2023 §7.3 §3.1 Hamiltonian Cycles: Dirac's Theorem, Bondy-Chvatal Matchings L 20 Wed, 5 Apr 2023 §3.1 QUIZ 5 (on HW 7 and 8) Matchings: Hall's Theorem hw10.pdf hw10.tex Week 12 L 21 Mon, 10 Apr 2023 §3.1 Konig-Egervary Theorem L 22 Wed, 12 Apr 2023 Connectivity, edge-connectivity Network flows Week 13 Mon, 17 Apr 2023 HOLIDAY (Patriot's Day) L 23 Wed, 19 Apr 2023 snow day? L 24 Fri, 21 Apr 2023 QUIZ 6 Algebraic graph theory, linear maps, eigenvalues, determinants Week 14 L 25 Mon, 24 Apr 2023 Probabilistic method, random graph models Wed, 26 Apr 2023 EXAM 2 (Note: not cumulative) Fri, 28 Apr 2023 PROJECT DUE: report.pdf and slides.pdf Week 15 Mon, 1 May 2023 Last day of class PROJECT presentations   6:00-8:00pm There will be pizza. And fabulous non-cash prizes! Week 16 No Final Exam Yay!

## Some important dates I got from Admin:

• FIRST day: Wed Jan 18
• DROP deadline: Wed Feb 8
• SPRING BREAK: March 20-24
• W or P/F deadline: Wed Apr 5
• PASSOVER: First two days Wed Apr 5, 6 - not a holiday but keep in mind
• LAST day: Mon May 1
• HOLIDAYS: Mon Feb 20, Mon Apr 17
• MAKE-UP DAY: Wed Apr 19 (currently no classes, could change?)
• SWAP DAYS: Thu Feb 23 = Tufts Monday, Fri Apr 21 = Tufts Monday

## Student Resources:

Accommodations for Students with Disabilities: Tufts University values the diversity of our students, staff, and faculty and recognizes the important contribution each student makes to our unique community. Tufts is committed to providing equal access and support to all qualified students through the provision of reasonable accommodations so that each student may fully participate in the Tufts experience. If you have a disability that requires reasonable accommodations, please contact the StAAR Center (formerly Student Accessibility Services) at StaarCenter@tufts.edu or 617-627-4539 to make an appointment with an accessibility representative to determine appropriate accommodations. Please be aware that accommodations cannot be enacted retroactively, making timeliness a critical aspect for their provision.

Academic Support at the StAAR Center: The StAAR Center (formerly the Academic Resource Center and Student Accessibility Services) offers a variety of resources to all students (both undergraduate and graduate) in the Schools of Arts and Science, Engineering, the SMFA and Fletcher; services are free to all enrolled students. Students may make an appointment to work on any writing-related project or assignment, attend subject tutoring in a variety of disciplines, or meet with an academic coach to hone fundamental academic skills like time management or overcoming procrastination. Students can make an appointment for any of these services by visiting the StAAR Center (Links to an external site.)website, which can be accessed by the URL of .

Mental Health Support: As a student, there may be times when personal stressors or emotional difficulties interfere with your academic performance or well-being. The Counseling and Mental Health Service (CMHS) provides confidential consultation, brief counseling, and urgent care at no cost for all Tufts undergraduates as well as for graduate students who have paid the student health fee. To make an appointment, call 617-627-3360. Please visit the CMHS website: http://go.tufts.edu/Counseling (Links to an external site.) to learn more about their services and resources.