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)

CA: Adam Xu (Adam.Xu@tufts.edu)

Office Hours:

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

Other texts you might look at:

Grading:

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:

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.