Lectures: TR 2:30-4:00, HNE 034 Office hours: TR 12:30-2:30, Ross N609 or by appointment E-mail: vidnyanszkyz_at_gmail_dot_com Textbook: Introduction to Graph Theory by Robin Wilson 5th ed (optional) Grading: assignments 20%, midterms 40%, final exam 40%; Exam: Apr 20, 2:00, ACW 006 Teaching Assistant: John Campbell Results
HomeworksYou may work in groups (of size maximum 3), but the groups have to be registered until 22nd of January here .
Homework 1, due: Jan 26.
Some practice problems for the first midterm. Solutions of the midterm Homework 2, due: Mar 9.
Some practice problems and the problem discussed on the lecture with solutions. Syllabus for the final exam. Solutions of the second midterm
TopicsWeek 1: Basic definitions, Königsberg bridges, Handshaking lemma.
Week 2: Examples of graphs, infinite graphs, bipartite graphs and digraphs; Eulerian graphs: characterization and algorithm.
Week 3: Hamiltonian graphs, Ore's theorem. Connectivity: estimation on the number of edges. Dijkstra's algorithm. Trees.
Week 4: Counting labelled trees, Prufer-codes.
Week 5: Searching trees, breadth and depth first search, braces, planarity.
Week 6: Euler's formula and Kuratowski's theorem, midterm.
Week 7: Planarity cont'd, graphs on other surfaces.
Week 8: Reading week.
Week 9: Ramsey's theorem, finite and infinite version.
Week 10: Ramsey's theorem wiht multiple colors, graph coloring: vertex coloring.
Week 11: Graph coloring: face and edge coloring.
Week 12: Hall's theorem, questions.
Week 13: Midterm, Menger's theorem.
Week 14: Flows.