#### General information

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

#### Homeworks

You 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

#### Topics

Week 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.