Math 350: Graph Theory and Combinatorics (Fall 2017)


Instructor – Jan Volec

Office: Burnside 1242
Office hours: Tuesday, 10:30am - 12:30pm
Contact: jan [AT] ucw [DOT] cz

Course information

Time: Tuesday and Thursday 8:35am - 9:55am
Location: Burnside 1B24
Course outline: PDF here
Lecture content: see below
Lecture notes: PDF here (Fall 2012, written by Tommy Reddad; Last updated: November 6, 2017)
The contents and the numbering of the results in the notes differ slightly from the ones in the course.
! New PDF here ! (Fall 2017, written by Ralph Sarkis; Last updated: December 5, 2017)
Assignments: see below

Final exam

Date: Tuesday 12.12. (open-book)
Location: Fieldhouse gym, rows #43-44
Final: PDF here
Mock final: PDF here
Mock solution: PDF here
Past finals: Fall 2013, Fall 2014, Fall 2015, Fall 2016

Midterm

Date: Thursday 19.10. (in-class, open-book)
Topics (until 10/10 incl.):Paths, Cycles, Trees, Euler tours, Hamilton cycles, Bipartite graphs, Matchings in bipartite graphs
Problems:PDF here
Past midterms: 2012 2013 2014 2015 2016

Pre-requisites & restrictions

Assignments

DateAssignmentDueSolution
Tue 12.9. Assignment #1 – Paths and CyclesThu 21.9. PDF here
Tue 19.9. Assignment #2 – TreesThu 28.9. PDF here
Tue 26.9. Assignment #3 – Components, Minimum Spanning Trees, Shortest PathsThu 5.10. PDF here
Tue 3.10. Assignment #4 – Eulerian Tours, Bipartite graphsThu 12.10. PDF here
Tue 10.10. Assignment #5 – Matchings in bipartite graphsThu 19.10. PDF here
Tue 17.10. Assignment #6 – Matchings in general graphsThu 26.10. PDF here
Tue 24.10. Assignment #7 – Ramsey TheoryThu 2.11. PDF here
Tue 31.10. Assignment #8 – Connectivity & Menger's theorem, Network flowsTue 14.11. PDF here
Tue 7.11. Assignment #9 – Vertex-coloringsTue 21.11. PDF here
Thu 16.11. Assignment #10 – Edge-colorings, Line graphsFri 24.11. PDF here
Tue 21.11. Assignment #11 – Planar graphsThu 30.11. PDF here
Mon 4.12. Assignment #00 – Additional problems for bonus / practiceTue 12.12. N/A

Content of the lectures

DateContent of the lectureLecture notesDiestel's book
Tue 5.9. Introduction to graph theory (see PDF slides from the first lecture) N/AN/A
Thu 7.9. Adjacency & incidence matrices, vertex-degree, walks, trails & paths Chapters 1, 2Chapter 1
Tue 12.9. Connected components, subgraphs and induced subgraphs, cut-vetices and cut-edgesChapter 2Chapter 1
Thu 14.9. Trees – various characterisations and their mutual equivalenceChapter 3Chapter 1
Tue 19.9. Number of graphs on n vertices and labelled trees on n vertices (Cayley's formula)PDF notesN/A
Thu 21.9. Spanning trees, fundamental cycles, Minimum spanning trees and Kruskal's algorithmChapter 4N/A
Tue 26.9. Shortest paths and Dijkstra's algorithmChapter 5N/A
Thu 28.9. Euler tours and Euler's theorem, Hamilton cycles and Ore / Pósa's theorem (statement)Chapter 6Chapters 1, 10
Tue 3.10. proof of Ore / Pósa's theorem, Bipartite graphsChapters 6, 7Chapters 2, 10
Thu 5.10. Regular graphs, matchings, 2-factors, König's theorem (statement)Chapter 8Chapter 2
Tue 10.10. proof of König's theorem, Hall's theorem and its applicationsChapter 8Chapter 2
Thu 12.10. Matching & covering inequalities, Tutte's theorem (statement), Petersen's theoremChapters 11, 13Chapter 2
Tue 17.10. proof of Tutte's theoremChapter 13Chapter 2
Thu 19.10. Midterm (in-class) N/AN/A
Tue 24.10. Ramsey numbers R(k), Ramsey's TheoremChapter 12Chapter 9
Thu 26.10. Exponential lower-bound on R(k), Multicolor Ramsey numbers & Shur's theoremChapter 12Chapters 9, 11
Tue 31.10. Vertex/edge k-connectivity, vertex/edge-cuts, Menger's/Ford-Fulkerson's theorem (statement)Chapter 9Chapter 3
Thu 2.11. Proof of Menger's theoremChapter 9Chapter 3
Tue 7.11. Flows in networks, Ford-Fulkerson TheoremChapter 10Chapter 6
Thu 9.11. Proof of Ford-Fulkerson's theorem, vertex coloringsChapters 10, 14Chapters 5, 6
Tue 14.11. Greedy coloring algorithm, d-degenerate graphs, Brooks' theorem (statement)Chapter 14Chapter 5
Thu 16.11. Coloring Δ-free graphs, edge colorings, König's line coloring, Vizing's, and Shannon's theoremsChapter 15Chapter 5
Tue 21.11. Planar graphs, drawings of planar graphs, regions, Euler's formulaChapter 17Chapter 4
Thu 23.11 Counting edges in planar graphs, Kuratowski's theorem, Minors in graphsChapters 17, 18Chapter 4
Tue 28.11 Duality of planar graphs, 5-Color theorem, Hadwiger's conjecture, K4-minor free graphsChapters 16, 19Chapter 5
Thu 30.11 FInal review, Mock final exam and its solution, Questions & Answers, 42N/AN/A

Further references & useful links

Grading policy

Course grades will be based upon assignments (20%), a midterm (20%), and a final exam (60%), or, assignments (20%) and a final exam (80%), if this leads to a better mark.