Math 350: Graph Theory and Combinatorics (Fall 2016)


Instructor – Jan Volec

Office: Burnside 1131
Office hours: Tuesday, 2pm - 4pm
Contact: jan [AT] ucw [DOT] cz

Course information

Time: Monday and Wednesday 2:35pm - 3:55pm
Location: Burnside 1B36
Course outline: PDF here
Lecture content: see below
Lecture notes: PDF here (Fall 2012, written by Tommy Reddad)
(The contents and the numbering of the results in the notes differ slightly from the ones in the course.)
Assignments: see below
Further problems: PDF here (Last update: November 23)

Final exam

Date: Thursday 8.12. (open-book)
Location: Fieldhouse gym, row #38
Final: PDF here
Mock final: PDF here
Mock solution: PDF here
Past finals: Fall 2013, Fall 2014, Fall 2015
Hint: Enjoy!

Midterm

Date: Monday 24.10. (in-class, open-book)
Topics:Paths, Cycles, Trees, Bipartite graphs, Matchings in bipartite graphs, Connectivity
Problems:PDF here
Solution:PDF here

Pre-requisites & restrictions

Assignments

DateAssignmentDueSolution
Mon 19.9. Assignment #1 – Paths, Cycles and TreesWed 5.10. PDF here
Mon 3.10. Assignment #2 – Bipartite graphs, Matchings, ConnectivityWed 19.10. PDF here
Mon 17.10. Assignment #3 – Menger's theorem and Network FlowsWed 2.11. PDF here
Mon 31.10. Assignment #4 – Ramsey Theory, Matchings, ColoringsWed 16.11. PDF here
Mon 14.11. Assignment #5 – Edge-colorings, Line graphs, Planar graphsWed 30.11. PDF here

Content of the lectures

DateContent of the lectureLecture notesDiestel's book
Fri 2.9. Introduction to graph theory (see PDF slides from the first lecture) N/AN/A
Wed 7.9. Adjacency & incidence matrix, vertex-degree, walks & paths, connected components Chapters 1 & 2Chapter 1
Mon 12.9. Subgraphs and induced subgraphs, various characterizations of treesChapter 3Chapter 1
Wed 14.9. Number of labelled trees on n vertices (Cayley's formula) – PDF notesN/AN/A
Mon 19.9. Minimum spanning trees and Kruskal's algorithmChapter 4N/A
Wed 21.9. Shortest paths and Dijkstra's algorithmChapter 5N/A
Mon 26.9. Euler tours and Euler's theorem, Hamilton cycles and Ore's theoremChapter 6Chapters 1 & 10
Wed 28.9. 2-factors, Bipartite graphs and Hall's theorem – PDF notesChapters 7 & 8Chapters 1 & 2
Mon 3.10. König's theorem and 2-factors in 2k-regular graphsChapters 8 & 15Chapter 2
Wed 5.10. Vertex-connectivity of graphs & vertex-cuts, Menger's theoremChapter 9Chapter 3
Wed 12.10. Edge-connectivity, edge-cuts, flows in networks, Ford-Fulkerson's theorem (statement)Chapters 9 & 10Chapters 3 & 6
Mon 17.10. Proof of Ford-Fulkerson's theoremChapter 10Chapter 6
Wed 19.10. Ramsey's Theorem & lower-bound on Ramsey numbersChapter 12Chapters 9 & 11
Mon 24.10. Midterm (in-class) – PDF hereN/AN/A
Wed 26.10. Multicolor Ramsey numbers & Shur's theorem, Matching & covering inequalitiesChapters 11 & 12Chapter 9
Mon 31.10. Matchings in general graphs & Tutte's theoremChapter 13Chapter 2
Wed 2.11. Petersen's theorem, Vertex colorings, Greedy coloring algorithm, Brooks' theoremChapter 14Chapter 5
Mon 7.11. Colorings of d-degenerate graphs, chromatic number of triangle-free graphsChapter 14Chapter 5
Wed 9.11. Exercise session – Connectivity & Hall & RamseyN/AN/A
Mon 14.11. Edge-colorings, Vizing's theorem, König's line coloring theorem, Shannon's theoremChapter 15Chapter 5
Wed 16.11. Planar graphs & Euler's formulaChapter 17Chapter 4
Mon 21.11. Counting edges in planar graphs, Outer-planar graphs, Kuratowski's TheoremChapter 15Chapter 4
Wed 23.11. Minors in graphs, Duality for planar graphs, 5-Color TheoremChapters 18 & 19Chapters 4 & 5
Mon 28.11. K4-minor free graphs, Extremal graph theory – Mantel's Theorem, Turán's TheoremChapter 16Chapter 7
Wed 30.11. Mock final exam - PDF hereN/AN/A
Mon 5.12. Final Review, 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.